[동적 계획법 1] [C++] 11054번. 가장 긴 바이토닉 부분 수열

www.acmicpc.net/problem/11054

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

 

 

입력

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

출력

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

---

해결 방법

이전 문제인 가장 긴 증가하는 부분 수열의 변형 문제이다. (아직 풀지 않았다면 아래 문제를 먼저 풀어보도록 하자.)

 

www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

문제를 보면 1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN 이러한 꼴을 만족하는 수열이 바이토닉 수열이라고 나와있다.

즉, 증가하는 수열이면서 동시에 감소하는 수열을 모두 포함하고 있는 형태이어야 한다.

 

1행은 주어진 입력 값, 2행은 가장 긴 증가하는 부분 수열의 길이이다.

1	5	2	1	4	3	4	5	2	1
1	2	2	2	3	3	4	5	5	5

 

순서를 반대로 놓고 (맨 뒤부터) 가장 긴 증가하는 부분 수열의 길이를 다시 구해보면 아래와 같은 결과가 나온다.

1	5	2	1	4	3	4	5	2	1
5	5	4	4	4	3	3	3	2	1

 

문제에서 주어진 것처럼 바이토닉 수열의 경우 증가하는 꼴이면서 감소하는 꼴, 두 가지 형태를 모두 지닌 수열이므로

위에서 구한 정방향, 역방향의 가장 긴 증가하는 부분 수열의 길이를 더한다. 그 결과, 아래와 같은 결과가 나온다.

1	5	2	1	4	3	4	5	2	1
6	7	6	6	7	6	7	8	7	6

 

하지만 여기서 주의할 점이 있다. 가장 큰 값인 8이 정답이 아니다.

그 이유는 증가하거나 감소하는 부분 수열을 셀 때 자기 자신 1개만 있어도 그 길이를 1로 계산해줬다.

이 값을 증가하는 수열과 감소하는 수열 모두 계산해줬기 때문에 값이 중복된다.

따라서 -1을 해줘야하고 정답은 7이 된다.

 

최종 코드는