https://www.acmicpc.net/problem/11054
주어진 수열에서 가장 긴 바이토닉 부분수열을 찾는 문제이다.
바이토닉 부분수열이란, 수열이 증가하다 특정 수를 기준으로 감소하는 수열이다.
예시에 나오듯이
- {10, 20, 30, 40}: 40 기준
- {10, 20, 30, 25, 20}: 30 기준
- {50, 40, 25, 10}: 50 기준
기존에 포스팅했던 증가하는 부분 수열의 방법을 참고해 어렵지 않게 풀었다.
복습할 겸 증가하는 부분 수열 문제의 경우 풀이를 생각해보자.
{10, 20, 30, 25, 20}을 기준으로 dp 배열을 준비한다
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| j | i |
i를 바깥, j를 안쪽으로 하는 이중 포문을 이용해 dp배열을 채울 것이다.
기본 길이를 1로 설정하였으므로 i는 1부터 시작한다.
j는 0부터 i 이전까지로 하여, i번째 숫자 앞의 숫자들만 순회한다.
j(0)번째 숫자는 10이고, i(1)번째 숫자는 20이므로 증가하는 수열이다.
따라서 dp[0]에 1을 더한 2를 dp[1]에 저장한다.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 2 | 1 | 1 | 1 |
| j | i |
이후 i를 2로 옮긴다.
먼저 j가 0인 경우에 0번째 숫자는 10이고 i(2)번째 숫자는 30이다. 오름 차순이므로 dp[2]에 dp[0] + 1의 값인 2를 저장한다.
다음 j가 1인 경우에 1번째 숫자는 20이고 i(2)번째 숫자는 30이다. 오름 차순이므로 dp[2]에 dp[1] + 1의 값인 3을 저장한다.
여기서 주의할 점이 있다, 현재 dp[i]의 값보다 dp[j] + 1의 값이 클 경우에만 dp[i]를 갱신해야 한다. 이걸 빠뜨릴 경우 최댓값을 보장할 수 없다.
이런 방식으로 이중 반복문을 진행하면 아래와 같은 i번째를 끝으로 하는 가장 긴 부분수열의 길이정보를 얻을 수 있다.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 2 | 3 | 3 | 2 |
바이토닉 부분 수열을 구하는 방법은 위 풀이방법을 생각하며 구할 수 있다.
{10, 20, 30, 25, 20} 을 기준으로
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 2 | 3 | 3 | 2 |
이러한 증가 dp배열을 구했다.
바이토닉 부분 수열은 기준이 되는 수까지 가장 긴 증가배열의 길이 + 기준이 되는 수부터 끝까지 가장 긴 감소배열의 길이 라고 할 수 있다.
따라서 증가 수열을 구하는 것처럼 가장 긴 감소 수열을 구해보자.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| i | j |
i를 N-1 위치부터 0까지 감소시키며, j는 i+1부터 N-1까지 반복하여 dp배열을 채운다.
i(3)번째 숫자는 25이고 j(4)번째 숫자는 20이므로 감소수열이다. 따라서 dp[3]에 dp[4] + 1의 값인 2를 저장한다.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 1 |
| i | j |
다음은 i를 1 감소시키고 j는 i+1인 3부터 4까지 반복한다.
i(2)번째 숫자는 30이고, j(3)번째 숫자는 25이므로 감소수열이다. 따라서 dp[2]에 dp[3] + 1의 값인 3을 저장한다.
다음 j를 1 증가시켜 4번째이다.
i(2)번째 숫자는 30이고, j(4)번째 숫자는 20이므로 감소수열이다. 하지만 dp[2]의 현재 값인 3보다 dp[4] + 1의 값인 2가 작으므로 갱신은 하지 않는다.
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 | 3 | 2 | 1 |
위 과정을 i가 0일 때까지 반복하면 위의 감소 배열이 나오게 되며, 그 의미는 i번째 숫자부터 시작하는 감소하는 수열의 최대 길이이다.
그럼 주어진 수열에 대해 가장 긴 증가 배열과 감소 배열을 각각 구했다.
{10, 20, 30, 25, 20}
증가 배열
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 2 | 3 | 3 | 2 |
감소 배열
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 1 | 3 | 2 | 1 |
증가 배열은 0번 부터 i번째 수를 마지막으로하는 가장 긴 부분 수열의 길이 이고
감소 배열은 i번째 수부터 마지막 수까지의 가장 긴 부분 수열의 길이이다.
이를 이용해 답을 구할 수 있다.
10, 20, 30, 25, 20 각 수들을 기준으로 하는 바이토닉 부분 수열의 최대 길이를 각 배열의 인덱스의 값 합 - 1이라고 정의할 수 있다.
2번 수인 30을 기준으로 한다면?
증가 배열[2]의 값인 3은 {10, 20, 30}을 의미하고
감소 배열[2]의 값인 3은 {30, 25, 20}을 의미한다.
두 길이를 더한 위 중복되는 기준 값(30) 하나를 제거하면 최댓값이 된다.
3번 수인 25를 기준으로도 생각해보자.
증가 배열[3]의 값인 3은 {10, 20, 25}를 의미하고
감소 배열[3]의 값인 2는 {25, 20}을 의미한다.
그럼 25를 기준으로 하는 바이토닉 부분 수열은 {10, 20, 25, 20}이 된다.
이를 구현한 코드이다.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val N = readLine().toInt()
val numbers = readLine().split(' ').map{it.toInt()}
val ascending = IntArray(N){1}
val descending = IntArray(N){1}
for(i in 0 until N){
for(j in 0 until i){
if(numbers[i] > numbers[j] && ascending[j] >= ascending[i])
ascending[i] = ascending[j] + 1
}
}
for(i in N - 1 downTo 0){
for(j in i until N){
if(numbers[i] > numbers[j] && descending[j] >= descending[i])
descending[i] = descending[j] + 1
}
}
var max = 0
for(i in 0 until N){
val sum = ascending[i] + descending[i] - 1
if(max < sum) max = sum
}
print(max)
}
위에서 이야기한 대로 ascending (증가 배열)과 descending(감소 배열)을 각각 준비하고 1로 초기화한다.
이후 각각 이중 포문을 이용해 i번째를 기준으로 하는 증가 배열의 최대 길이, 감소 배열의 최대 길이를 구해 각 배열에 저장한다.
그리고 각 숫자를 기준으로 하는 바이토닉 부분 수열의 길이를 구한 뒤, 그들 중 최댓값을 출력한다.
