[백준/boj][C++/cpp] 11054번: 가장 긴 바이토닉 부분 수열

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

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

---

---

(풀이)

바이토닉 수열을 2개로 나누어 보자 

특정한 위치 pos에 대하여

 - pos까지 증가하는 수열 

 - pos부터 감소하는 수열

 

 두 수열에서 최대 길이를 저장하는dp_increase[], dp_decrease[]을 정의하고,

Tabulation을 이용하여 2개의 배열에 값을 넣는다.

 

그 후 특정 pos ( = 바이토닉 수열에서 최대인 값 )으로 바이토닉 수열의 최대 길이를 구한다.

len = dp_increase[pos] + dp_decrease[pos] - 1

( - 1을 하는 이유 : pos가 중복되므로)

---

(코드) - Tabulation

#include <iostream>
using namespace std;

int N;
int ar[1000];
int dp_increase[1000];
int dp_decrease[1000];

int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++)cin >> ar[i];
	
	for (int i = 0; i < N; i++) {
		dp_increase[i] = 1;
		dp_decrease[i] = 1;
	}
	for (int i = 1; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if (ar[i] > ar[j])dp_increase[i] = max(dp_increase[i], dp_increase[j] + 1);
		}
	}

	for (int i = N-2; i >=0; i--) {
		for (int j = N-1; j > i ; j--) {
			if (ar[i] > ar[j])dp_decrease[i] = max(dp_decrease[i], dp_decrease[j] + 1);
		}
	}

	int maxLen = 0;
	for (int i = 0; i < N; i++) {
		maxLen = max(maxLen, dp_increase[i] + dp_decrease[i] - 1);
	}
	cout << maxLen;
}

---

내가 틀렸던 부분

이전과 마찬가지로 초기화 과정에서 문제가 생겼다.

수열의 길이이므로 dp의 원소는 최소 1의 값을 가진다고 생각을 하였고

여느때와 마찬가지로 dp[0] = 1;로 초기화를 하여 문제를 풀었다.

 

하지만 dp[]를 갱신할때, if문에 해당하지 않으면 dp[]에 값이 할당되지 않으므로 비쥬얼 스튜디오에서는 임의로 0의 값이 주어져서 계산이 되었다.

 

이를 방지하기 위해 모든 dp의 원소를 1로 초기화 하는 과정이 필요하다

 

너무 습관적으로 코드를 작성하지 말고 과정과 이유를 생각하면서 코드를 작성해야겠다....