[백준]동적 계획법1/가장 긴 바이토닉 부분 수열/11054 풀이 JAVA

문제

수열 S가 어떤 수 Sk를 기준으로 S(1) < S(2) < ... < S(k-1) < S(k) > S(k+1) > ... > S(N-1) > S(N)을 만족한다면,

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

예를 들어, {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를 이루고 있는 A(i)가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A(i) ≤ 1,000)

 

출력

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

 

풀이(JAVA)

전에 풀었던 <가장 긴 증가하는 부분 수열(백준-11053)>의 응용문제인 듯하다.

https://min-wachya.tistory.com/56

[백준]동적 계획법1/가장 긴 증가하는 부분 수열/11053 풀이 JAVA

위의 문제를 잘 이해했다면 이번 문제는 쉽게 풀 수 있을 것이다.

(LDS(최장 감소 부분 수열)은 LTS를 반대로 응용하기만 하면 되기 때문에)

 

예제 하나를 살펴보자.

A = {1, 5, 2, 1, 4, 3, 4, 5, 2}라고 하자.(백준 문제의 예제와는 다름)

 

이제 

S(1) < S(2) < ... < S(k-1) < S(k) > S(k+1) > ... > S(N-1) > S(N)

위의 조건을 만족시키는지 검사를 해야하는데

 

조건 1 : S(1) < S(2) < ... S(k-1) < S(k)

조건 2 : S(k) > S(k+1) > ... > S(N-1) > S(N)

으로 나눠서 문제를 풀어보도록 하자.

 

dp1은 LTS를 이용하여 조건 1을 검색하고,

dp2는 LDS를 이용하여 조건 2를 검색한다.

index	0	1	2	3	4	5	6	7	8
A	1	5	2	1	4	3	4	5	2
dp1	1	2	2	1	3	3	4	5	2
dp1의 부분 수열	{1}	{1, 5}	{1, 2}	{1}	{1, 2, 4}	{1, 2, 3}	{1, 2, 3, 4}	{1, 2, 3, 4, 5}	{2}
dp2	1	4	2	1	3	2	2	2	1
dp2의 부분 수열	{1}	{5, 4, 3, 2}	{2, 1}	{1}	{4, 3, 2}	{3, 2}	{4, 2}	{5, 2}	{2}

 

이때 최댓값은 A[7]인 5가 S(k)인 수열의 길이이다.

수열의 길이는 dp1[7] + d2[7] - 1로 나타내는데 이는 중복된 자기 자신의 요소를 뺀 것이다.

즉 최댓값은 5 + 2 - 1인 6이 된다.

 

---

까악 검색 안 하고 혼자 풀었다!!

백준 알고리즘 문제 중에... 가장 간단하게 푼 듯...(우와~^^

재밌다 잘 풀리니까