백준 2229) 조 짜기

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

2229번: 조 짜기

 

문제

알고스팟 캠프에 N(1≤N≤1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학생들을 같은 조로 묶어서 서로 자극을 받으며 공부하도록 만들기 위함이다. 따라서 가급적이면 실력 차이가 많이 나도록 조를 편성하는 것이 유리하다.

하지만 조를 편성할 때 같은 조에 속하게 된 학생들의 나이 차이가 많이 날 경우에는 오히려 부정적인 효과가 나타날 수도 있다. 따라서 선생님들은 우선 학생들을 나이 순서대로 정렬한 다음에, 적당히 학생들을 나누는 방식으로 조를 짜기로 하였다. 조의 개수는 상관이 없다.

각각의 조가 잘 짜여진 정도는 그 조에 속해있는 가장 점수가 높은 학생의 점수와 가장 점수가 낮은 학생의 점수의 차이가 된다. 또한 전체적으로 조가 잘 짜여진 정도는, 각각의 조가 잘 짜여진 정도의 합으로 나타난다. 한 명으로 조가 구성되는 경우에는 그 조의 잘 짜여진 정도가 0이 된다(가장 높은 점수와 가장 낮은 점수가 같으므로).

학생들의 점수가 주어졌을 때, 조가 잘 짜여진 정도의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 다음 줄에는 N명의 학생들의 점수가 나이 순서대로 주어진다. 각 학생의 점수는 0 이상 10,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

 

---

 

접근 방법

 

우리는 두 가지의 조건을 눈 여겨 봐야 한다.

 

1. 각각의 조가 잘 짜여진 정도는 가장 높은 점수를 받은 학생과 가장 낮은 점수를 받은 학생의 차이
2. 전체적으로 조가 잘 짜여진 정도는 각각의 조가 잘 짜여진 정도의 합

 

 

이 조건들로부터 알 수 있는 것은 어떤 학생을 조에 포함해야 전체적으로 조가 잘 짜여진 정도를 알 수 있냐는 것이다.

즉, 임의의 i번 째 학생을 포함하여 조를 짜기 이전에 i-1번 째의 전체적으로 조가 잘 짜여진 정도는 무슨 값인지 모른다.

이전의 상태를 모를 때, memozation 기법을 통해 이전의 상태를 저장한 다이나믹 프로그래밍으로 풀어야 함을 알 수 있다.

 

 

위의 설명을 그림으로 표현해보면 다음과 같다.

 

 

 

그래서 D[n] = n번 째로 조가 잘 짜여진 정도를 나타낸다.

그럼 각각의 조는 어떻게 DP로 접근할 수 있을까?

 

i-1번 째로 조가 잘 짜여진 정도에 속해있는 학생들과 i번 째 학생의 최댓값과 최솟값의 차이를 구하면 된다.

그래야 i번 째로 조가 잘 짜여진 정도를 나타낼 수 있기 때문이다.

 

i번 째 학생을 기준으로 i-1 학생부터 0번 째 학생까지 차이를 구한다.

편의를 위해 범위를 j ( 0 < j < i-1) 설정하겠다!

 

 

 

위의 분석들을 종합해서 점화식을 세워본다면 다음과 같다.

 

D[i] = maxOf(D[i], D[j] + maxOf(A[i], A[j]) - minOf(A[i],A[j]))
i ( 0 < i <= n)
j ( 0 < j < i-1)

 

 

소스 코드

 

a는 0번 째 배열부터 시작하므로 편의를 위해 j의 범위를 i부터 1까지 설정했다.

 

fun main() = with(System.`in`.bufferedReader()) {
    var n = readLine().toInt()
    val a = readLine().split(" ").map { it.toInt() }
    val dp = IntArray(1001)

    for(i in 1..n) {
        for(j in i downTo 1) {
            val max = maxOf(a[i-1], a[j-1])
            val min = minOf(a[i-1], a[j-1])

            dp[i] = maxOf(dp[i], dp[j-1] + max - min)
        }
    }
    println(dp[n])
}