백준 11053 증가하는 부분 수열

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

주어진 수열의 부분 수열 중 가장 긴 증가하는 수열을 찾는 문제이다.

입력되는 수열의 크기가 최대 1000이므로 O($n^2logn$) 이내의 알고리즘으로 풀어야 할 것 같다.

이 문제는 dp 문제 유형으로 일차원 dp 배열에 각 수열의 원소마다 해당 원소를 마지막으로 하는 증가 수열의 최대 길이를 저장하는 방식을 사용한다.

위 예제 수열인
[10 20 10 30 20 50] 의 경우
[1 2 1 3 2 4] 의 dp 배열을 만드는 것이다.

dp배열을 만드는 과정을 알아보면, 최초에는 모두 1로 초기화시킨다.

10	20	10	30	20	50
1	1	1	1	1	1

제일 앞의 10은 원소가 하나인 수열이므로 넘어가고 커서를 두 번째 위치인 20으로 설정한다.

10	20	10	30	20	50
1	1	1	1	1	1

20을 기준으로, 앞에 있는 원소들과 비교하여 그 원소보다 현재 원소(20)이 큰 경우 앞의 원소의 dp값에 1을 더한 값을 현재 dp값에 저장한다.

위의 경우 첫 번째 원소인 10보다 현재 위치(2번째)의 20이 더 크므로, 첫 번째 원소인 10의 dp값인 1에 1을 더한 값인 2를 저장한다.

10	20	10	30	20	50
1	2	1	1	1	1

다음은 커서가 3번째 값인 10으로 이동한다.
앞에있는 원소들(10, 20)들과 비교했지만 현재 위치의 값이 더 크지 않으므로 값을 바꾸지 않고 넘어간다.

10	20	10	30	20	50
1	2	1	1	1	1

다음은 커서가 4번째 값인 30으로 이동한다.

먼저 첫 번째 위치의 값인 10과 비교하고, 현재 값인 30이 더 크므로 10의 dp값인 1에 1을 더한 값인 2를 30위치의 dp값에 저장한다.

다음으로 두 번째 위치의 값인 20과 비교하여, 20의 dp값인 2에 1을 더한 3을 저장한다.

마지막으로 세 번째 위치의 값인 10과 비교하여, 10의 dp값인 1에 1을 더한 값인 2가 있는데, 20과 비교하여 저장한 3 값보다 작으므로 최대 수열을 구하기 위해서 3을 그대로 놔둔다.

10	20	10	30	20	50
1	2	1	3	1	1

같은 방법으로 다섯번째 값인 20은 앞의 값들 중 10보다만 크므로 2가 저장된다.

10	20	10	30	20	50
1	2	1	3	2	1

마지막 값인 50도 유사하게, 앞의 모든 값들보다 크므로 각 앞의 dp값 + 1의 값 중 가장 큰 4(30 값 다음으로 연결)를 저장한다.

10	20	10	30	20	50
1	2	1	3	2	4

그러면 구하고자 하는 결과를 얻을 수 있다.

가장 긴 부분수열 값은 위 dp배열의 값들 중 최댓값에 해당한다.

import kotlin.math.max

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val seq = readLine().split(' ').map{it.toInt()}

    val dp = IntArray(N){1}

    for(i in 1 until N){
        for(j in 0 until i){
            if(seq[j] < seq[i]){
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
    }
    print(dp.maxOrNull())
}

위 과정에 대한 코드이다. 길이가 길지 않다

바깥 반복문은 1부터 끝까지, 안쪽 반복문은 처음부터 i까지 반복하며 현재 값보다 작은 앞의 값들의 dp값 + 1 중 최댓값을 저장한다.