[백준]11054 가장 긴 바이토닉 부분 수열 (Kotlin)

문제 설명

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

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

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

---

풀이 과정

이 문제는 이 문제의 하위버전인 가장 긴 증가하는 부분수열 문제(https://www.acmicpc.net/problem/11053)를 풀었다면 쉽게 접근할 수 있는 문제이다.

 

먼저, 길이 10짜리 수열을 보자.

1 5 2 1 4 3 4 5 2 1

일단은, 감소하는 부분은 생각하지 말고 인덱스별로 증가하는 부분만을 생각해보자.

5는 1 -> 5 로 증가하기 때문에 길이 2짜리 부분수열이며

2는 1 -> 5 -> 2 가 될 수 없기 때문에 1 -> 2 로 2이다.

1은 증가할 수 없기 때문에 1이며

4는 1 -> 2 -> 4 이기 때문에 3이다.

 

이러한 식으로 부분증가 수열 중 최대 길이를 찾아내야 하는데,

이는 기준점(i)을 2번째 인덱스부터 끝점까지 반복문을 통해 이동해주며

그 안에서의 다른 기준점(j)을 세워 처음부터 i번째 인덱스 이전까지 돌며

 

i번째 수보다 작은 수를 만났을 경우에 그 수까지 부분수열의 길이에 +1을 해주면 된다.

 

즉, 2중 for문을 통해 i번째 인덱스에 대해 그 인덱스의 부분수열을 구해주면 된다.

참고로, 배열 길이는 1000이므로 2중 for문을 돌더라도 시간초과가 발생하지 않는다.

---

이를 그대로, 감소하는 수열에 적용해보자.

 

이번엔 기준점(i)을 처음 2번째 인덱스가 아닌 마지막에서 2번째 인덱스를 두어 감소하도록 하고

그 안의 기준점(j)을 끝점부터 i번째 인덱스 까지 돌며

 

i번째 수보다 작은 수를 만났을 경우에 그 수까지의 부분수열의 길이에 +1을 해주면 된다.

 

이를 코틀린 코드로 나타내면 다음과 같다.

import kotlin.collections.*
import kotlin.math.max

fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val list = readLine()!!.split(" ").map { it.toInt() }

    val upDp = Array(1001){1}
    val downDp = Array(1001){1}

    for(i in 1 until n) {
        for(j in 0 until i) {
            if(list[i] > list[j]) {
                upDp[i] = max(upDp[i], upDp[j] + 1)
            }
        }

    }

    for(i in n-2 downTo 0) {
        for(j in n-1 downTo i+1) {
            if(list[i] > list[j]) {
                downDp[i] = max(downDp[i], downDp[j] + 1)
            }
        }
    }

    var max = 0
    for(i in 0 until n) {
       if(upDp[i] + downDp[i] > max) {
           max = upDp[i] + downDp[i]
       }
    }

    print(max-1)
}

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !