백준[3980] - 선발 명단 (Kotlin)

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val stat = Array<Array<Int>>(11) { emptyArray() }
    val selected = Array(11) { 0 }
    var max = Int.MIN_VALUE

    val N = br.readLine().toInt()

    fun dfs(k: Int, sum: Int) {
        if (k >= 11) {
            max = max(max, sum)
            return
        }

        var nonZero = 0
        for (i in 0 until 11) {
            // 선수에 해당하는 경우의 수를 모두 찾았다면 재귀 탈출
            if (nonZero >= 5) return
            // 이미 선발된 포지션이거나 적합하지 않은 포지션일 경우 continue
            if (selected[i] == 1 || stat[k][i] == 0) continue
            // 적합한 포지션인 경우 nonZero count ++
            if (stat[k][i] != 0) nonZero ++
            selected[i] = 1
            dfs(k + 1, sum + stat[k][i])
            selected[i] = 0
        }
    }

    repeat(N) {
        max = Int.MIN_VALUE
        for (i in 0 until 11) {
            stat[i] = br.readLine().split(" ").map { it.toInt() }.toTypedArray()
        }
        dfs(0, 0)
        bw.write(max.toString() + "\n")
    }

    bw.flush()
    bw.close()
    br.close()
}

 

첫번째 선수부터 모든 포지션에 대한 최댓값의 경우의 수를 백트래킹을 통해 확인한다.

선발된 포지션에 대한 상태를 저장하기 위해 selected 배열을 사용하였다.

각 포지션 i = 0~10에 대해 selected[i] == 1(이미 선발된 포지션) 이거나 stats[k][i] == 0(선수의 해당 포지션이 적합하지 않음)

일 경우 continue한다.

stats[k][i] != 0일 경우 nonZero++ 를 통해 적합한 포지션의 수를 증가한다.

(* 문제 조건 : 모든 선수에게 적합한 포지션의 수는 최대 5개이다.)

for문에서 nonZero가 5 이상일 경우 나머지 포지션에 대해서는 모두 능력치가 0인 경우이므로 재귀를 탈출한다.

 

고찰 : 조건과 테스트케이스에 쫄지 말자. 결국에는 백트래킹이다. 지금까지는 문제 분류가 백트래킹인 걸 알고 애초에 백트래킹으로 풀 작정으로 들어갔지만 슬슬 문제를 보았을 때 백트래킹으로 풀어야 하는 문제인지 아닌지를 판단할 수 있는 능력을 길러야 할 것 같다.

 

걸린 시간 : 20분

난이도 : 골드 4

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

3980번: 선발 명단