11054번 : 가장 긴 바이토닉 부분 수열

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

11054번: 가장 긴 바이토닉 부분 수열

 

 

 

못 풀어서 해설을 본 문제.

 

증가하는 부분 수열을 두 번 이용하면 풀 수 있는 문제.

 

DP 정의가 복잡해지고 있다면, 문제의 해결 접근 방법이 맞는지 다시 생각해봐야 한다.

 

 

 

---

 

 

 

해설코드(C++).

 

 

 

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int arr[1001];
int dp[1001][2];
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    dp[1][0] = 1;
    dp[1][1] = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= i - 1; j++) {
            dp[i][0] = 0;
            dp[i][1] = 0;
            for (int k = 0; k < 2; k++) {
                if (k == 0) {
                    if (arr[i] > arr[j]) {
                        dp[i][0] = max(dp[i][0], dp[j][0] + 1);
                    }
                    else if (arr[i] < arr[j]) {
                        dp[i][0] = max(dp[i][0], dp[j][0]);
                        dp[i][1] = max(dp[i][1], dp[j][0] + 1);
                    }
                    else {
                        dp[i][0] = max(dp[i][0], dp[j][0]);
                    }
                }
                else {
                    if (arr[i] > arr[j]) {
                        dp[i][1] = max(dp[i][1], dp[j][1]);
                    }
                    else if (arr[i] < arr[j]) {
                        dp[i][1] = max(dp[i][1], dp[j][1] + 1);
                    }
                    else
                        dp[i][1] = max(dp[i][1], dp[j][1]);
                }
            }
        }
    }
 
    cout << max(dp[N][0], dp[N][1]) << endl;
    return 0;
}