백준 2229번: 조 짜기

문제: https://www.acmicpc.net/problem/2229

문제 풀이

DP

$dp[i] =$ $0$ 번째 학생부터 $i$ 번째 학생까지 조를 짰을 때 점수의 최댓값

$dp[i] = max_{0 <= j <= i} ( dp[j-1] + (max_{j <= k <= i} A_k - min_{j <= k <= i} A_k) )$ (단, $dp[j-1]$은 $j=0$일 때 $0$으로 취급)

모든 $i$에 대해 $dp$ 테이블을 구하면 $dp[N-1]$이 정답

풀이 설명

문제에서 학생들을 나이 순서대로 정렬한 다음에, 적당히 학생들을 나누는 방식으로 조를 짠다고 나와있는데, 이는 조를 연속된 순서의 학생들로 짜야 한다는 뜻이다.

문제에서 주어진대로 연속된 N명의 학생에 대한 순서가 주어졌을 때 조를 짠다고 생각해보자. 그리고 이를 두 부분으로 나눈다고 생각하면 마지막 학생이 포함된 조와 그 이전까지 학생들의 조로 나눌 수 있다.

이렇게 나눈다면 현재 구해야 하는 값이 조의 점수 최댓값이기 때문에 현재 확인해야 하는 마지막 학생이 포함되는 조의 점수 최댓값과 이전까지 학생들의 조의 점수 최댓값으로 나눌 수 있다. 이 때 이전까지 학생들의 조의 점수 최댓값을 알고 있다면 값을 더 쉽게 구할 수 있다.

이에 따라 $dp[i] =$ $0$ 번째 학생부터 $i$ 번째 학생까지 조를 짰을 때 점수의 최댓값이라고 정의하면 다음과 같이 점화식이 나온다.

$dp[i] = max_{0 <= j <= i} ( dp[j-1] + (max_{j <= k <= i} A_k - min_{j <= k <= i} A_k) )$ (단, $dp[j-1]$은 $j=0$일 때 $0$으로 취급)

따라서 점화식에 따라 $dp$ 테이블을 구하면 $dp[N - 1]$이 정답이 된다.

그리고 점화식을 코드로 구현할 때 i번째 학생이 포함된 조의 점수를 구하기 위해 조에 포함된 학생의 점수 최댓값, 최솟값을 구해야 한다.

이때 j를 i부터 0까지의 역순으로 확인해야 하는 이유는 조가 연속된 순서의 학생들로 이루어져야 하고 i번째 학생이 이 조의 마지막 순서이므로 조에 포함된 학생의 점수 최댓값, 최솟값을 구할 때 매번 조에 포함된 모든 학생들의 점수를 다시 확인하지 않고 j 번째 학생의 점수만 확인해 최댓값, 최솟값을 갱신할 수 있기 때문이다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val N = br.readLine().toInt()
    val students = br.readLine().split(" ").map{it.toInt()}
    val dp = IntArray(N){ 0 }
    for(i in 0 until N){
        var max = students[i]
        var min = students[i]
        for(j in i downTo 0){
            if(min > students[j]) min = students[j]
            if(max < students[j]) max = students[j]
            val sum = (if(j != 0) dp[j - 1] else 0) + max - min
            if(dp[i] < sum) dp[i] = sum
        }
    }
    println(dp[N-1])
}