[Baekjoon]11054.가장 긴 바이토닉 부분 수열(DP)

Baekjoon

#11054

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

---

LIS문제의 원리를 이용하여 풀 수 있는 문제 중 하나이다. LIS 문제 해결 방법은 이전 포스팅을 참고하자. 여기

처음에는 i번째 수까지는 증가 수열, i번째 수 이후 부터는 감소 수열을 이루는 방법으로 접근했다. 두 문제 모두 풀어본 다음에 이 문제를 접했기 때문에 그런 아이디어를 떠올렸는데 반복문을 돌때 i도 변하는데 이 때 배열 d에 저장되는 값에 문제가 있는 것 같았다. 내가 구현을 못한거 같기도 하다. 다른 사람들의 풀이는 대부분 양방향에서 LIS를 사용하는 방법을 사용했다. 의미상 내가 생각했던 방법과 같지만 구현하는데 있어서 더 쉬운 방법인것 같다.

배열 a, d는 LIS 문제와 같이 정의하고 다음과 같이 푼다.

처음에는 왼쪽에서 오른쪽방향으로 LIS 문제를 푼다. 여기까지는 11053번 문제랑 같다. 

그 다음에는 오른쪽에서 왼쪽방향으로 LIS 문제를 푼다. 오른쪽에서 왼쪽방향으로 증가 수열이면 원래 방향에서는 감소 수열이다. d[n]에 값을 저장할때도 오른쪽부터 저장한다. 

그렇게해서 나온 두 배열의 원소끼리 모두 더한 후 1을 뺀 값이 바이토닉 수열의 길이이다. 1을 빼는 이유는 길이를 저장할때 양쪽에서 한번씩 자신의 길이를 더하기 때문에 한 번이 중복되서 더해지는 것이므로 최종 답을 구할 때는 1을 빼주는 것이다. 이 값이 최대가 되는 값이 바이토닉 수열의 최장 길이다. 위 그림에서는 8이 최댓값이고 1을 뺀 7이 답이다. 이것은 부분 수열 {1, 2, 3, 4, 5, 2, 1}의 길이이다.

배열 d를 2차원으로 생성하여 d[0][i]에 첫번째 LIS의 길이, d[1][i]에 두번째 LIS의 길이를 저장했다. 

<코드>

		for (int i = 1; i < n; i++) { // 왼 --> 오 LIS
			for (int j = 0; j < i; j++) {
				if (a[i] > a[j]) {
					if (d[0][i] < d[0][j] + 1) {
						d[0][i] = d[0][j] + 1;
					}
				}
			}
		}

		for (int i = n - 2; i > 0; i--) { // 오 --> 왼 LIS
			for (int j = n - 1; j > i; j--) {
				if (a[i] > a[j]) {
					if (d[1][i] < d[1][j] + 1) {
						d[1][i] = d[1][j] + 1;
					}
				}
			}
		}

<전체코드>