백준, BOJ, 11053번, 가장 긴 증가하는 부분 수열 : C++ [CPP]

항상 N번째 일때는 어떻게 해야 가장 길어질까?

이전의 어느 원소를 가져와야할까??

생각을 해보자

 

 

 

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

 

---

#맞는 풀이

#include <iostream>
#include <algorithm>

using namespace std;
const int MAX = 1001;

int N;
int arr[MAX];
int dp[MAX];


int main(){
    cin >> N;
    
    int ans = 0;
    
    for(int i = 1; i<=N; i++){
        int x;
        cin >> x;
        arr[i] = x;
    }
    //초기값
    fill(dp, dp+1001, 1); //자기자신은 항상 포함되므로 최소 1
    for(int i = 1; i<=N; i++){
        for(int j = 1; j<i; j++){
            if(arr[i]>arr[j]){
               dp[i] = max(dp[i], dp[j] + 1);
            }    
        }
        ans = max(ans, dp[i]);
    }
    
    cout << ans;
    
    
    return 0;
}

 

 

N번째가 가장 길려면 이전의 증가하는 부분 수열 중에서

1)해당 부분 수열의 값이 나보다 작아야하고 2)가장 긴 것을 가져오면 된다.

그렇게 되면

1번 조건 때문에 증가하는 수열이라는 규칙을 지킬 수 있고

2번 조건 때문에 가장 긴 것도 가져오게 된다.

 

하지만 어떤 것인지 모르기 때문에 N번째라면 1~N-1을 모두 탐색해야 한다.

다만 Memoization을 통해 미리 계산해서 저장한다.