백준 11054 가장 긴 바이토닉 부분 수열 (C++)

 부분 수열 시리즈 3번째이다. https://tigerfrom2.tistory.com/33 먼저 이 문제를 풀고 왜 dp를 쓰는지 알고 오는 것이 좋다.

백준 11053 가장 긴 증가하는 수열(C++)

매우 비슷한 문제이지만 dp의 갱신 조건이 더 까다로워졌다. 위 문제는 증가하기만 하면 +1로 갱신이 편리했지만 바이토닉 수열은 따질 것이많다.

우선 바이토닉 수열이 무엇인지 알아야한다.

바이토닉은 증가하다가 감소하는 수열이다. 여기서 순증가나 순감소 수열도 바이토닉 수열에 포함됨이 중요하다.

그렇다면 dp 갱신 조건은 3가지 임을 알 수 있다.

1. 오름차순

2. 내림차순

3. 오름차이다가 내림차순

 

예를 들어보자 1 5 6 3 9 가 들어온다고 해보자.

1. 1이 들어오면 dp[1] = 1이다.

2. 5가 들어오면 1 5 이고 오름차순 : 1 - 5 , 내림차순 5, 바이토닉 1 - 5 이므로 dp[5] = 2 이다.

3. 6이 들어오면 1 5 6 이고 오름차순 : 1 - 5 - 6, 내림차순 5, 바이토닉 1 - 5 - 6 이므로 dp[6] = 3 이다. 

4. 3이 들어오면 1 5 6 3 이고 오름차순 : 1 - 3, 내림차순 6 - 3, 바이토닉 1 - 5 - 6 - 3 이므로 dp[3] = 4이다.

5. 9가 들어오면 1 5 6 3 9 이고 오름차순 : 1 - 5 - 6 - 9 내림차순 9, 바이토닉 1 - 5 - 6 - 9 dp[9] = 4이다. 

 

자 그렇다면 여기서 내림차순으로 dp 갱신이 된적이 있나? 없다! 왜냐하면 내림차순이라면 4번을 예로 들면 3이 들어왔을 때 6  ,3 이 내림차인데 이는 곧 dp[6]의 바이토닉 수열의 길이 + 1 과 같다. 즉 내림차순 갱신은 바이토닉 갱신에 포함되어있다는 것이다. 

그리고 난 여기서 dp 배열을 구조체로 오름차만 저장하는 수와 바이토닉을 저장하는 수를 함께 만들어두었다. 왜냐하면 1 5 6 7 4 9 라고 치면 dp[4] = dp[7]의 오름차순 + 1 이 된다. 그런데 dp[9]가 들어오면 4보다 크므로 4의 바이토닉 + 1 이 되어 잘못된 정보를 내놓기 때문에 바이토닉은 내림차일때만 갱신되어야한다.

 

#include <iostream>

using namespace std;

typedef struct DP {
	int increas;
	int bytonic;
}DP;

int main() {
	int arr[1001] = { 0, };
	DP dp[1001];
	int n;
	int answer = 1;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		dp[arr[i]].bytonic = 1;
		dp[arr[i]].increas = 1;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[arr[i]].increas = max(dp[arr[i]].increas, dp[arr[j]].increas + 1);
				dp[arr[i]].bytonic = max(dp[arr[i]].bytonic, dp[arr[j]].increas + 1);
			}
			if (arr[i] < arr[j]) {
				dp[arr[i]].bytonic = max(dp[arr[i]].bytonic, dp[arr[j]].bytonic + 1);
			}

			int tmp = max(dp[arr[i]].increas, dp[arr[i]].bytonic);
			answer = max(tmp, answer);
		}
	}

	cout << answer << endl;
}

0ms!