백준 11568번 민균이의 계략

전형적인 DP문제이다.

DP를 워낙 못하다보니, 계속해서 DP에 익숙해지고 감잡는데 초점을 맞춘다...

 

알고리즘 풀이

입력 배열 : 입력받은 입력 배열값. 설명에서 vec이라 하겠음.

dp배열 : 해당 인덱스가 최대값일 때, 수열의 최대 원소 갯수값

 

해당 문제는 점화식이 따로 있다기 보다는 증가하는 수열의 기본적인 문제였다. 

(1) 현재 vec의 인덱스 i의 원소가 하위(vec[1] ~ vec[i-1]) 원소보다 커야하는 것과 

(2) (1)의 조건에 해당하는 원소 중, 길이가 가장 긴 값을 가져와서 dp배열에 +1한 수를 넣는다.

 

설명이 어렵다면 코드를 보면서 이해를 추가하기를 바랍니다.

 

#include <iostream>
#include <vector>

using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    vector<int> dp(N, 0);
    dp[0] = 1;
    for(int i=1; i<N; i++) {
        int maxi = 0;

        for(int j=i-1; j>=0; j--) {
            if(vec[j] < vec[i]) {
                if(maxi < dp[j])
                    maxi = dp[j];
            }
        }

        if(maxi == 0) dp[i] = 1;
        else dp[i] = maxi + 1;
    }

    int ans = 0;
    for(int i=0; i<N; i++) {
        if(ans < dp[i])
            ans = dp[i];
//        cout << dp[i] << ' ';
    }

    cout << ans;

    return 0;
}

코드 리뷰는 언제나 환영입니다!