백준 1182 코틀린

fun main() {
    val (n, s) = readln().split(" ").map { it.toInt() }
    val inputs = readln().split(" ").map { it.toInt() }
    dfs(null, inputs, n, s, 0)
    println(answer)
}

var answer = 0
fun dfs(sum: Int?, inputs: List<Int>, n: Int, s: Int, startIndex: Int) {
    if (sum == s) {
        answer++
    }

    for (i in startIndex until n) {
        dfs((sum ?: 0) + inputs[i], inputs, n, s, i + 1)
    }
}

무난한 백트래킹 문제이므로 dfs를 이용해서 풀 수 있습니다.

 

다만 주의해야할 부분은 보통이라면 dfs의 sum에 초깃값으로 0을 넣습니다.

즉 위의 코드에서 4번째 줄을 보통

dfs(0, inputs, n, s, 0)

이렇게 하고 푸는 게 일반적인 백트래킹 문제들의 풀이법인데

 

이 문제는 inputs로 들어온 숫자에 양수, 음수가 섞여 있고, s가 0이 될 수 있기 때문에

sum에 초기값으로 0을 집어넣게 되면 아무 것도 안 했는데 dfs의 if(sum == s)에 충족되어서

answer가 +1 되어버립니다.

 

따라서 s가 0인 경우엔 문제가 생기므로 sum의 초기값을 null로 설정하였습니다.