[Baekjoon] 11722번

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 30 10 20 20 10

예제 출력 1 복사

3

 

코드 답안

#include  <stdio.h>
int main(){
    int *arr = NULL,*index=NULL,N,cnt=0,maxcnt=0;
    scanf("%d",&N);
    arr = (int *)malloc(sizeof(int)*N),index = (int *)malloc(sizeof(int)*N);
    for(int i=0;i<N;i++){
        scanf("%d",&arr[i]); index[i] = 1;
        /*값을 입력받고 현재 인덱스의 배열값을 1로 초기화한다.*/
        for(int j=0;j<i;j++) if(arr[j]>arr[i] && index[i] < index[j] + 1) index[i] = index[j] + 1;
        /*현재 인덱스까지 반복하여 해당 조건 만족 시 문장을 수행한다.
        1. 이전 인덱스의 요소가 현재 인덱스의 요솟값보다 큰 경우.
        2. 현재 색인의 인덱스(배열)의 값이 이전 색인의 인덱스(배열)값의 +1보다 작은 경우

        현재 색인의 인덱스(배열)값을 업데이트 한다.
         */
        if(maxcnt < index[i]) maxcnt = index[i];}//최대 길이를 저장한다.,
    printf("%d",maxcnt);
}

 

풀이:  예제 1 입력 가정

index[i]	1	1	1->2(2,1)	1->2(3,1)	1->2(4,1)	1->2(5,1) ->3(5,3)
	j = 0	j = 1	j = 2	j = 3	j = 4	j = 5
i = 0	10
i = 1	10	30
i = 2	10	30	10
i = 3	10	30	10	20
i = 4	10	30	10	20	20
i = 5	10	30	10	20	20	10
결과값	1	1	2	2	2	3

비교 대상 값(arr[i])	밑줄
조건 1 만족 시	빨강
조건 2 만족 시	파랑
두 조건 모두 만족 시	초록