[BOJ/11722] 가장 긴 감소하는 부분 수열

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

- https://www.acmicpc.net/problem/11722

 

사용 알고리즘

- DP

 

풀이

- d[i] = a[i]를 가장 마지막으로 하는 가장 긴 감소하는 부분 수열의 길이

- d[i] = max(d[j]) + 1 (j < i, a[j] > a[i])

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/11722.cpp

#include <cstdio>   int d[1003]; int a[1003];   int main(void) {     int n; scanf("%d", &n);     for (int i = 0; i < n; ++i) scanf("%d", &a[i]);     int ans = -1;     for (int i = 0; i < n; ++i) {         d[i] = 1;         for (int j = 0; j < i; ++j) {             if ((a[i] < a[j]) && (d[j] + 1 > d[i])) d[i] = d[j] + 1;         }         if (ans < d[i]) ans = d[i];     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs