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

www.acmicpc.net/problem/11054

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

코드

#include <iostream>
using namespace std;

int n;
int A[1000];
int inc_arr[1000];
int dec_arr[1000];
int len = 0;
int max(int a, int b){
	return a > b ? a : b;
}

void init(){
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> A[i];
	}
}

void solve(){
	for(int i=0; i<n; i++){
		inc_arr[i] = 1;
		dec_arr[i] = 1;
		for(int j=0; j<i; j++){
			if(A[i] > A[j]){
				inc_arr[i] = max(inc_arr[i], inc_arr[j] + 1);
			}
			if(A[i] < A[j]){
				dec_arr[i] = max(inc_arr[j] + 1, dec_arr[i]);
				dec_arr[i] = max(dec_arr[i], dec_arr[j] + 1);
			}
		}
		len = max(inc_arr[i], len);
		len = max(dec_arr[i], len);
	}
	cout << len;
}
int main() {
	init();
	solve();
	return 0;
}

문제

지문 자체가 난해한 문제는 아닙니다. 문제 그대로

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면,

그 수열을 바이토닉 수열이라고 한다.

이 바이토닉 수열을 찾으면 되는 문제죠.

 

풀이

단순히 계속 증가해서 커지는 수열만 찾는것도, 계속 감소해서 작아지는 수열만 찾는것도 아닙니다.

두 개 다 찾아야 하죠. 계속 증가하다가 계속 감소하는 수열을 찾아야 하기 때문에 

각 각의 수열의 길이를 저장할 배열을 두 개 선언하겠습니다.

int n; // 수열을 이루는 수의 개수 n
int A[1000]; // 수열 A
int inc_arr[1000]; // 증가하는 수열
int dec_arr[1000]; // 감소하는 수열
int len = 0; // 최장길이

따라서 변수의 선언은 위와 같습니다.

그럼 이것을 활용해서 어떻게 풀 수 있을까요?

다른 블로그 글 같은걸 보니, 대부분은 이제

(왼쪽에서 오른쪽으로 증가하는 수열길이) + (오른쪽에서 왼쪽으로 증가하는 수열 길이) - 1

이렇게 해서 풀이를 하셨습니다. 근데 저 같은 경우에는 조금 다르게 풀었는데요.

우선, 정답이 될 수 있는 경우의 수에 대해 잠깐 짚고 넘어가겠습니다.

• 계속해서 증가하는 수열이 가장 긴 경우
• 계속해서 감소하는 수열이 가장 긴 경우
• 증가하다 감소하는 수열이 가장 긴 경우

해서 점화식도 세 개 정도로 생각하면 될 것 같습니다.

1. 계속 증가하는 수열

이 문제는 

wonsang98.tistory.com/77

백준 11053번: 가장 긴 증가하는 부분 수열(C++)

제가 여기서 풀이를 작성해 놨습니다. 이 풀이랑 똑같이해서 증가하는 수열의 개수를 알아냅니다.

inc_arr[i] = max(inc_arr[i], inc_arr[j] + 1)

2. 계속해서 감소하는 수열

이는 1번의 반대로 해주면됩니다.

1번의 조건이 A[i] > A[j] 였다면, 2번의 경우는 작아져야하니 A[i] < A[j]가 되겠죠.

dec_arr[i] = max(dec_arr[i], dec_arr[j] + 1)

3. 증가하다 감소하는 수열

A[i] < A[j] 인 경우, 즉 감소하는 조건일 때

이전까지 증가하고 있던 수열 inc_arr[j] + 1 값입니다.

dec_arr[i] = max(dec_arr[i], inc_arr[j] + 1)

 

위의 세 개의 점화식의 계산 값 중 가장 큰 값이 정답이 됩니다.

또한, 틀렸는데 어디서 틀렸는지 모르시는 분들은 

www.acmicpc.net/board/view/56223

글 읽기 - 가장 긴 바이토닉 수열 반례 및 필독FAQ 모음

여기서 반례를 한 번 찾아보시길 추천드립니다.