✍️ 코테 준비/Dynamic Programming

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

고도고도 2021. 2. 1. 18:37

www.acmicpc.net/problem/11054

 

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

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

www.acmicpc.net

 

 

입력

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

출력

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


해결 방법

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

 

www.acmicpc.net/problem/11053

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

문제를 보면 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이 된다.

 

최종 코드는