BOJ 11722 - 가장 긴 감소하는 부분 수열

www.acmicpc.net/problem/11722

11722번: 가장 긴 감소하는 부분 수열

 

DP 로 풀어야하는 문제이다.

int arr[MAX] 는 입력 받은 값

int dp[MAX] 는 

dp[a] = b; a 번째 index 까지의 최대길이가 b 이다. 를 의미한다.

 

dp 배열을 채워넣기 위해서

아래의 두가지 사항을 고려한다

 

첫번째, 현재 인덱스(i) 보다 작은 인덱스(j) 가 가르키는 값(arr[j]) 가 현재 인덱스가 가르키는 값(arr[i]) 보다 큰가?

즉, if (arr[i] < arr[j]) ? 인가

 

두번째, 현재 인덱스의 이전 인덱스(j) 를 선택하면, 현재 인덱스의 길이값이 더 길어 지는가?

즉, if (dp[j] + 1 > dp[i]) ? 인가

 

위 두가지 조건을 만족하는 경우

dp[i] = dp[j] + 1; (길이 하나 늘림)

 

- c++

#include <iostream>
 
#define MAX 1001
 
using namespace std;
 
int N, answer;
int arr[MAX], dp[MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> arr[i];
 
    for (int i = 0; i < N; ++i) {
        dp[i] = 1;
        for (int j = 0; j <= i; ++j) {
            if (arr[i] < arr[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }
    
    for (int i = 0; i < N; ++i)
        answer = max(answer, dp[i]);
        
    cout << answer;
    
    return 0;
}

 

 

 

 

 

 

 

DP 는 아무리 봐도 어렵다.