백준 #11053. 가장 긴 증가하는 부분 수열

백준 #11053. 가장 긴 증가하는 부분 수열

정리

• 모든 부분 수열의 길이는 1부터 시작한다. (수열의 길이가 1일 때의 정답은 1임을 생각해 보면 알 수 있다.)
• 이전 상태(최적 부분 구조)를 어떻게 정의하고 저장해 둬야 할까?

이 문제는 간단한 예시를 들어 보면 훨씬 이해가 빠를 것 같다.
수열 A를 { 1, 2, 1, 3, 2, 4 } 이라 하자.

1. 첫 번째 숫자까지만 고려할 때, 가능한 증.부.수(증가하는 부분 수열)는 { 1 } 로 길이는 1이다.

2. 두 번째 숫자까지 고려할 때, 이전 수들 중 2보다 더 작은 숫자로 [1] 이 있다. 1의 부분 수열의 길이가 1이었으므로, 가장 증.부.수는 { 1, 2 } 로 길이는 2이다.

3. 세 번째 숫자를 고려해 보면, 이전 수들 중 1보다 더 작은 숫자는 없다. 따라서 세 번째 숫자에서의 증.부.수는 { 1 } 로 길이는 1이다.

4. 네 번째 숫자를 고려해 보면, 이전 수들 중 3보다 더 작은 숫자는 [1, 2, 1] 이 있다. 이들 중에서 증.부.수를 가장 길게 만들려면 가장 ‘2의 증.부.수'의 뒤에 3를 붙인 { 1, 2, 3 } 로 만들어야 한다. 이때 길이는 3이다.

5. 다섯 번째 숫자를 고려해 보면, 이전 수들 중 2보다 더 작은 숫자는 [1, 1] 이 있다. 둘 다 증.부.수의 길이는 1이다. 따라서 다섯 번째 숫자의 증.부.수는 { 1, 2 } 로 길이는 2이다.

6. 여섯 번째 숫자를 고려해 보면, 이전 수들 중 4보다 더 작은 숫자는 [1, 2, 1, 3, 2] 가 있다. 각각 증.부.수의 길이는 [1, 2, 1, 3, 2]이다. 3일 때가 증.부.수의 길이가 가장 기므로 여섯 번째 숫자의 증.부.수의 길이는 여기에 1을 더한 4이다.

결과적으로 답은 4이다.

위와 같은 방식으로 동적 계획법을 적용하면 된다. 요약하자면, i번째 숫자의 가장 긴 증가하는 부분 수열의 길이는
“1 ~ i-1번째 숫자들 중에서 i번째 숫자보다 더 작은 숫자들 중 증가하는 부분 수열의 길이가 가장 긴 것에 1을 더한 값”이다.

정답 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void) {
    int N;
    int A[1001];   // 값 저장
    int dp[1001];  // 가장 긴 증가하는 부분 수열의 길이 저장
    int res = 0;
    
    cin>>N;
    for(int i=1; i<=N; i++) {
        cin>>A[i];
        dp[i] = 1;   // 모든 증가하는 부분 수열의 기본 값은 1
    }
    
    dp[1] = 1;
    res = 1;
    for(int i=2; i<=N; i++) {
        for(int j=1; j<=i; j++) {
            if(A[i] > A[j]) dp[i] = max(dp[j] + 1, dp[i]);
        }
        res = max(res, dp[i]);
    }
    
    cout<<res<<endl;
    
    return 0;
}