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

BOJ 바로가기

#include <iostream>
using namespace std;
int a[1001], p[1001], m[1001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++) {
		p[i] = 1;
		for (int j = 1; j < i; j++) {
			if (a[i] > a[j] && p[i] < p[j] + 1) {
				p[i] = p[j] + 1;
			}
		}
	}
	for (int i=n; i >= 1; i--) {
		m[i] = 1;
		for (int j = i + 1; j <= n; j++) {
			if (a[i] > a[j] && m[i] < m[j] + 1) {
				m[i] = m[j] + 1;
			}
		}
	}
	int max;
	for (int i = 1; i <= n; i++) {
		if (i == 1)
			max = p[1] + m[1] - 1;
		else
			if (max < p[i] + m[i] - 1) {
				max = p[i] + m[i] - 1;
			}
	}
	cout << max;
	return 0;
}

📌회고

점화식을 어떻게 세워야 할지 고민하다가 n에서 가장 긴 증가하는 수열의 길이, 가장 긴 감소하는 수열의 길이 두 가지를 구해주면 답을 구할 수 있을 거란 생각이 들었다. 다만 아직 내 풀이에 확신이 없는 탓에 틀린 아이디어에 오랜 시간을 지체하게 될까봐 정답 소스코드를 확인했다. 다행히 정답 소스코드에 녹아있는 아이디어와 내 아이디어가 일치했다. 그대로 밀고 갔어도 괜찮았겠다는 생각이 들어 정답을 미리 확인한 게 못내 아쉬었지만 m[n]을 구하는 과정을 나름대로 잘 구현한 것 같아 뿌듯하다.

📌아이디어

앞서 말했듯 n에서 가장 긴 증가하는 수열의 길이, 가장 긴 감소하는 수열의 길이를 구하는 점화식을 각각 세워주면 된다.

나는 증가하는 수열의 길이를 p[n], 감소하는 수열의 길이를 m[n]으로 세워주었다. p[n]은 이전의 유사한 문제들에서 많이 구현해봐서 어렵지 않았지만 m[n]을 구현하는 과정이 조금 까다로웠다. 반복문을 많이 써봤지만 아직도 많이 익숙해져야 할 것 같다.

p[n]과 m[n]의 점화식을 세워준 후 p[n]+m[n]-1의 최댓값을 구해주면 이 문제의 정답을 도출해낼 수 있다. 이때 -1은 중복해서 더해진 n에서의 길이를 하나 빼 준 것이다.