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

문제 설명

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

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

•  

[문제]

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

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

[입력]

 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

[출력]

 첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

[예제 입력 1]

10
1 5 2 1 4 3 4 5 2 1

[예제 출력 1]

7

[힌트]

 예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

---

풀이

 문제를 보았을 때 바이토닉 수열의 특징을 찾아보자면 우선 특정 중심 값을 기준으로 왼쪽은 오름차순, 오른쪽은 내림차순으로 정렬되어야 한다. 그러기 때문에 계속 오름차순이거나 내림차순인 수열이 바이토닉 수열이라고 할 수 있지만 내림차순으로 정렬되다 오름차순으로 정렬된 수열을 바이토닉이라고 하지 않는다. 그럼 결국 특정 중심 값을 기준으로 왼쪽으로 가장 긴 오름차순 수열과 오른쪽으로 가장 긴 내림차순 수열을 찾아내면 된다.

 이를 해결하기 위해 단순 완전 탐색으로 가장 긴 수열을 찾아내는 것보다는, 다이나믹 프로그래밍으로 복잡성을 최대한 줄이고자 했다. 우선 가장 긴 오름차순 수열을 찾아야 하는 경우 수열의 왼쪽부터 시작하며, 가장 첫 번째 수열 요소의 경우 캐시 벡터에 자동적으로 길이 1을 넣는다. 이후 특정 중심 값이 오른쪽으로 이동할수록 자신의 인덱스보다 작은 인덱스들의 캐시 벡터를 찾아 그 중 수열의 값이 자신보다 작고 수열 길이가 가장 큰 값에 +1을 하여 자신의 캐시 배열에 넣는 과정을 반복한다.

1

5

2

1

4

3

4

5

2

1

입력 수열

1

2

2

1

3

3

4

5

2

1

이를 바탕으로 생성된 오름차순 수열 캐시 배열

 

 마찬가지로 내림차순의 경우 수열의 오른쪽에서 시작하여 위의 과정을 반복하면 된다.

1

5

2

1

4

3

4

5

2

1

입력 수열

1

5

2

1

4

3

3

3

2

1

이를 바탕으로 생성된 내림차순 수열 캐시 배열

 

 이후 해당 캐시 배열들이 완성되면 캐시 배열을 순회하여, 동일 인덱스 값에서 각 캐시 배열 값의 합-1 이 가장 큰 것을 골라 그 값을 반환하면 해당 값이 가장 긴 바이토닉 부분 수열이 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
//내림차순 수열 길이 최대값 찾기
void findDSC(vector<int>& dscCache, vector<int>& sequence, int N, int high) {

	for (int i = N - 1; i > high; i--) {
		if (sequence[i] < sequence[high] && dscCache[i] >= dscCache[high])
			dscCache[high] = dscCache[i] + 1;
	}
	//가장 왼쪽 요소의 경우 자동적으로 길이가 1
	if (dscCache[high] == -1)
		dscCache[high] = 1;

	return;
}
//오름차순 수열 길이 최대값 찾기
void findASC(vector<int>& ascCache, vector<int>& sequence, int N, int high) {

	for (int i = 0; i < high; i++) {
		if (sequence[i] < sequence[high] && ascCache[i] >= ascCache[high])
			ascCache[high] = ascCache[i] + 1;
	}
	//가장 오른쪽 요소의 경우 자동적으로 길이가 1
	if (ascCache[high] == -1)
		ascCache[high] = 1;

	return;
}
//메인 함수
int main() {
	int N, temp, answer = 0;
	vector<int> sequence;

	cin >> N; //수열의 크기 입력
	//수열 구성 입력
	for (int i = 0; i < N; i++) {
		cin >> temp;
		sequence.push_back(temp);
	}
	//캐시 배열 생성
	vector<int> ascCache(N, -1);
	vector<int> dscCache(N, -1);
	//오름차순 캐시 배열 채우기
	for (int i = 0; i < N; i++)
		findASC(ascCache, sequence, N, i);
	//내림차순 캐시 배열 채우기
	for (int i = N - 1; i >= 0; i--)
		findDSC(dscCache, sequence, N, i);
	//최대 길이 찾기
	for (int i = 0; i < N; i++) {
		answer = max(answer, ascCache[i] + dscCache[i] - 1);
	}

	cout << answer;

	return 0;
}

---

결과