[백준] 14225번 부분수열의 합(브루트포스 - DFS)[Kotlin - 코틀린]

백준 14225번 문제입니다. (solved.ac) 기준 실버 1 문제입니다.

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

14225번: 부분수열의 합

문제

문제 접근

수열 s가 주어지고 이 수열 s의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제입니다.

모든 부분 수열을 찾기 위하여 조합을 구현하였습니다. 조합의 시간 복잡도는 2^n이고 수열의 길이는 최대 20 이므로 조합하는 과정에서의 시간 복잡도는 2^20(1048576) 이므로 시간적 여유가 충분히 있다고 판단하였습니다.

모든 부분 수열을 찾은 후 모든 부분 수열들의 합을 찾아 중복되지 않도록 집합(Set)에 저장합니다.

 

1 ~ 모든 부분 수열들의 합 중 최댓값 까지 탐색을 시작하고 탐색중인 값이 모든 부분 수열의 합을 저장한 집합에 포함되어있지 않다면 해당 값이 수열 s의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수이다. 

만약 끝까지 탐색하였는데 모든 값이 부분 수열의 합들이 저장된 집합에 존재한다면 그 중 최댓값 보다 1 큰 값이 s의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수가 됩니다.

정답 코드

val sumOfSbSequenceSet = mutableSetOf<Int>()
lateinit var sequence: List<Int>
val subSequence = mutableListOf<Int>()

fun main() {

    val n = readln().toInt()
    sequence = readln().split(" ").map { it.toInt() }

    for (depth in 1..n) {
        dfs(0, depth, 0)
    }

    for (no in 1..sumOfSbSequenceSet.maxOf { it }) {
        if (!sumOfSbSequenceSet.contains(no)) {
            println(no)
            return
        }
    }

    println(sumOfSbSequenceSet.maxOf { it } + 1)
}

fun dfs(cnt: Int, depth: Int, beginWith: Int) {

    if (cnt == depth) {
        sumOfSbSequenceSet.add(subSequence.sum())
        return
    }

    for (index in beginWith until sequence.size) {
        subSequence.add(sequence[index])
        dfs(cnt + 1, depth, index + 1)
        subSequence.removeAt(subSequence.lastIndex)
    }

}