백준 1633 최고의 팀 만들기 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/1633

1633번: 최고의 팀 만들기

문제

꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플레이어의 흑,백 능력치는 각각 1부터 100까지의 정수로 주어진다. 대회가 진행되는 동안 플레이어는 흑, 백 중 한 가지만으로 참여를 해야하며 팀의 전체 능력치는 흑 플레이어의 능력치를 합한것과 백 플레이어의 능력치를 합한것을 모두 더한 값이다. 어떻게 하면 꿍 협회는 가능한 높은 능력치의 팀을 만들수 있을까.

입력

입력은 각 플레이어들의 능력치로 이루어진다. 각 줄은 공백으로 구분되는 두 개의 정수로 주어진다. 첫 번째 숫자는 해당 플레이어가 백으로 플레이를 할 때 능력치고 두 번째 숫자는 흑으로 플레이를 할 때의 능력치다. 최소한 30줄 이상이며 1000줄은 넘지 않는다.

출력

꿍 협회가 만들 수 있는 팀 중 가장 큰 능력치를 갖는 팀의 능력치를 출력한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

dp 문제이다.

3개의 옵션이 있다.

i 번째 사람을 백 팀에 넣기

i 번째 사람을 흑 팀에 넣기

i 번째 사람을 쓰지 않기

 

dp[i][w][b] = i번째 사람을 정할 때 백 팀에 w명, 흑 팀에 b명 있을 때 최댓값

 

dp[i][w][b] = dp[i-1][w-1][b] + whiteScore vs dp[i-1][w][b-1] + blackScore vs dp[i-1][w][b]

 

dp[i-1][w-1][b] + whiteScore == i 번째 사람을 백 팀에 넣는 경우

dp[i-1][w][b-1] + blackScore == i 번째 사람을 흑 팀에 넣는 경우

dp[i-1][w][b] == i 번째 사람을 쓰지 않는 경우 

 

i 값과 상관없이 w==15, b==15인 경우에 최댓값을 출력하면 된다.

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()

fun main() = with(System.out.bufferedWriter()) {
     //input
    val scoreList = ArrayList<List<Int>>()
    var input = br.readLine()
    scoreList.add(emptyList())
    while (!input.isNullOrBlank()) {
        input = input.trim()
        scoreList.add(input.split(' ').map { it.toInt() })
        input = br.readLine()
    }
    val dp = Array(scoreList.size + 1) { Array(16) { IntArray(16) } }
    var answer = 0
    //solve
    for (i in 1 until scoreList.size) {
        for (w in 0..15) {
            for (b in 0..15) {
                val white = if (w > 0) dp[i - 1][w - 1][b] + scoreList[i][0] else 0
                val black = if (b > 0) dp[i - 1][w][b - 1] + scoreList[i][1] else 0
                dp[i][w][b] = dp[i - 1][w][b].coerceAtLeast(white.coerceAtLeast(black))
                if (w == 15 && b == 15) {
                    answer = answer.coerceAtLeast(dp[i][w][b])
                }
            }
        }
    }
    //output
    write("$answer")
    close()
}