백준 11053번, 가장 긴 증가하는 부분 수열( C, C++)

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

#include<iostream>
#include<algorithm>

using namespace std;


int main(){
    int dp[1001] = {};
    int s[1001] = {};
    int N;


    int cnt;

    cin>>N;

    for(int i = 0; i < N; i++){
        cin>>s[i];
    }

    for(int i = 0; i < N; i++){
         dp[i] = 1;
         for(int j = 0; j < i; j++){
           if(s[i] > s[j]){
              dp[i] = max(dp[i], dp[j]+1);  
           }
        }
        cnt = max(dp[i], cnt);
    }
    cout<< cnt << endl;
    return 0;
}

 

개인적인으로 DP문제를 풀 때 처음부터 예시의 규모를 작게 잡았다가 확장하는 식으로 생각하는 것이 도움되었다.

 

수열 A = {1, 2, 1, 3}이 있다고 생각해보자

첫 번째 1의 부분 수열은 자기자신 1이므로 길이가 1이다.

두 번째 2의 부분 수열은 자기자신과 2이므로 길이가 2이다.

세 번째 1의 부분 수열은 첫 번째 1과 마찬가지로 길이가 1이다.

네 번째 3의 부분 수열의 경우는

{1 , 2, 3} , {1, 3} , { 2, 3} 이렇게 3가지의 경우가 있다.

그 중에서 길이가 가장 큰 것은 3이다.

여기서 규칙성을 찾아야하는데, 가장 길이가 커야하므로

자신 이전에 크기가 작은 수열 중에서, 제일 큰 경우의 부분 수열 길이를 + 1을 해주면 되는 규칙성을 찾았다.