백준(Baekjoon)_11722번 문제풀이

이거 정답비율 64%인거 치고 너무 어려웠다.

아마 이것과 비슷한 문제가 있어서 그걸 풀고 온 사람들 덕에 높은 것 같음.

 

일단 저 말부터 이해가 잘 안갔음.

 

가장 긴 감소하는 부분 수열이란,

ex) 1 9 3 7 6 2

이렇게 있으면 1을 기준으로 가장 긴 감소하는 부분 수열은 자기자신 1 하나.

그러므로 1.

6을 기준으로하면 9 7 6 해서 길이는 3.

2를 기준으로 하면 9 7 6 2 해서 길이는 4.

 

 

 

기준이 되는 수	1	9	3	7	6	2
	1	1	2	2	3	4

이렇게 이 수열은 앞숫자와 관련이있다.

앞수의 감소되는 수열 길이에서 +해나가는 것이라고 보면 됨.

 

역시 난 구글링을 하였고..

그나마 간단하게 코드 짜본게 이거다.

 

#include <stdio.h>
int main(void)
{
    int n, i, j;
    int arr[1000];
    int arr2[1000], max = 0;
 
    scanf("%d", &n);
 
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    for (i = 0; i < n; i++){
        arr2[i] = 1;
        for(j = 0; j < i; j++){
            if(arr[i] < arr[j] && arr2[i] < arr2[j] + 1)
                arr2[i] = arr2[j] + 1;
        }
    }
 
    for (i = 0; i < n; i++){
        if(max < arr2[i])
            max = arr2[i];
    }
    printf("%d\n", max);
 
}

 

솔직히 어려움.

내가 푼거지만 구글링을 해서그런가.. 100%이해하기는 어려움.

디버깅하면서 어 그런가보다 하는 중.

 

 

/0205

 

 

 

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받을 수 있습니다.