[c++] 백준 #11568 민균이의 계략 (190915)

< 풀이 >

딱 봤을 때 DP문제 같았다. 가장 긴 증가하는 부분 수열 구하기 문제이다.

1) O(N^2) 풀이 (N <= 1000이라 가능)

DP[n] : n까지 있을 때 최장 부분 수열의 길이로 정의하면,

DP[n] = max(DP[n-1]+1, DP[*]+1)으로 점화식을 세울 수 있다.

→ 현재 원소 이전에 현재 원소보다 더 작은 값을 O(N)에 찾을 수 있따.

 

2) O(NlogN) 풀이(구현은 안해봄)

LIS 후보를 크기 순서로 붙인 후 lower bound를 찾고 고쳐준다. 그러고 나면 그 수열의 길이가 LIS의 길이와 동일하다. 이 수열이 LIS라는 것은 아님. LIS 후보들을 다시 뜯어보면, 길이 1짜리 IS 마지막 수 중 가장 작은 수

** 앞의 수와 상관없이 맨 뒤에 있는 수가 중요한 DP의 성질

이 방법대로 하면 logn으로 lower bound를 구할 수 있다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<int> A(N, 0);
    vector<int> DP(N, 1);
    // DP[i] = A[i]를 포함한 부분 수열 중 가장 긴 것의 길이
    // 자기 자신만 포함하는 경우를 대비하여 1로 초기화
    for(int i=0; i<N;i++){
        cin >> A[i];
    }
    int ans = DP[0];
    // O(N^2)
    for(int i=1; i<N;i++){
        for(int j=0; j<i;j++){
            if (A[j] < A[i]){ 
                DP[i] = max(DP[i], DP[j] + 1);
            }
        }
        ans = max(DP[i], ans);
    }
    cout << ans << '\n';
    return 0;
}