[Kotlin] 백준(BOJ) 11053 가장 긴 증가하는 부분 수열

문제 전문은 아래 버튼을 눌러 확인하실  수 있습니다.

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

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

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 

예제 입출력

문제 해설

가장 긴 증가하는 부분 수열을 구하는 문제이다. 문제에 나와있듯이 연속하는 위치를 잡을 필요는 없다. 

해당 문제는 분할 정복을 이용한 생각으로 해결 방향을 도출할 수 있다. 다만 약간의 응용이 필요하다

 

예제 입력 1을 예시로 들었을 때

먼저 첫 번째 수, 10까지만 존재하는 수열임을 가정했을 때 증가 수열의 길이는 당연히 1이다. 그렇다면 두 번째 수까지 고려한다면 당연히 10보다 크므로 수열의 길이는 2이다.

 

여기까지만 생각하면 다음과 같은 불완전한 점화식을 도출할 수도 있다.

 

현재 수열의 값이 지금까지 최장 증가 수열의 값보다 큰 경우 ( $sequence[i] > sequence[i - 1]$  이면 )

현재까지의 수열의 최장 증가 수열의 길이 = 지금까지의 최장 증가 수열의 길이 + 1 ( $dp[i] = dp[i + 1] + 1$ )

 

현재 수열의 값이 지금까지 최장 증가 수열의 값보다 작은 경우 ( $sequence[i] > sequence[i - 1]$ )

현재까지의 수열의 최장 증가 수열의 길이 = 지금까지의 최장 증가 수열의 길이 ( $dp[i] = dp[i + 1]$ )

 

언뜻 보면 말이 되는 것 같지만 이는 다음과 같은 경우를 고려하지 못한다. 

 

최장 증가 수열이 첫 번째 부터 시작하지 않는 경우

 

이 경우가 잘 이해되지 않으면 다음과 같은 예시에  대입해보면 이해할 수 있을 것이다.

$10, 1, 2, 3, 4 ,5$

 

따라서 최장 증가 수열은 모든 위치에서 시작될 수 있다는 것을 염두에 두고 점화식을 도출하여야 한다. 방법은 아까와 유사하다. 

우선 첫 번째는 아까와 동일하다. 10까지의 수열은 최장 증가 수열의 길이가 1이다, 두 번째 수 20 또한 이전 수인 10보다 크므로 20까지의 최장 증가 수열의 길이는 당연히 2이다. 

세 번째 수  10을 보면, 이는 지금까지 이어오던 증가 수열에 포함될 수 없다. 아까와 달리 여기서 이 값을 버리는 것이 아니라 최장 증가 수열이 이 값에서 시작될 수 있는 경우를 고려해 기록해야 한다. 

 

그렇다면 그 다음값 (네 번째 수)30은 20, 10보다 크므로 다음과 같은 선택이 가능하다. 

첫 번째 수(10)에서 끝나는 증가 수열, (두 번째 수)20에서 끝나는 증가 수열, (세 번째 수)10에서 끝나는 증가 수열 중 더 긴 길이의 뒤에 붙기

이 중에서 (두 번째 수)20에서 끝나는 증가 수열이 가장 크므로 길이 2를 선택해 +1을 하여 가져오면 될 것이다. 

 

그 다음값 (다섯 번째 수)20보다 작은 값은 (첫 번째, 세 번째)10뿐이므로 다음과 같은 선택이 가능하다.

첫 번째 수(10)에서 끝나는 증가 수열, (세 번째 수)10에서 끝나는 증가 수열 중 더 긴 길이의 뒤에 붙기

이 중에서는 어떤 것을 고르던 결과가 같다. 즉 길이 1을 선택해 + 1을 가져오면 된다.

 

결론적으로 다음과 같은 점화식을 도출할 수 있다. 

$dp[n]$은  $sequence$의 $n$번째 숫자로 종료되는 가장 긴 수열의 길이이다.  

$dp[n] = max[sequence[i]\ 가\ sequence[n]보다\ 작은\ 모든\ i\ 들에\ 대한\ dp[i] 값들]$

 

최종적으로 $dp[n]$은 전체를 고려한 최대 길이가 아닌 $n$번째 숫자로 끝나는 최장 증가 수열의 길이이다. 

전체 $dp$에 대해 $max()$를 취해야 문제에서 최종적으로 구하고자 하는 값이 도출된다. 

 

 

소스 코드

 

fun main() {
    val sequenceSize = readln().toInt()
    val sequence = readln().split(" ").map { it.toInt() }

    val dp = mutableListOf<Pair<Int, Int>>()
    dp.add(0 to 0) // 기저값 세팅

    for (i in sequence) {
        val maxLen = dp
            .filter { it.second < i }
            .maxOf { it.first }

        dp.add(maxLen + 1 to i)
    }

    println(dp.maxOf { it.first })
}

 

 

시간 복잡도

for()문 내에서 max값을 구하는 연산을 수행하므로 $O(N^2)$이라고 할 수 있다.