백준 14225 부분수열의 합 Kotlin (부분집합)

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

14225번: 부분수열의 합

문제

수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오.

예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 수 있다. 하지만, 4는 만들 수 없기 때문에 정답은 4이다.

입력

첫째 줄에 수열 S의 크기 N이 주어진다. (1 ≤ N ≤ 20)

둘째 줄에는 수열 S가 주어진다. S를 이루고있는 수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 출력한다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

조합 기본 문제이다.

조합이라기보단 부분 집합이지만, 본인은 조합/순열로 보통 구분하고, 그 로직 안에 분기 처리로 결괏값을 컨트롤한다.

조합으로 모든 부분 집합을 구하여 graph에 visit처리하고, 이후 1부터 200만까지 탐색하여 방문하지 않은 값을 바로 출력하면 된다.

 

코드

val br = System.`in`.bufferedReader()

fun getIntGraph() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var input: List<Int>
val visited = BooleanArray(2000001)
val graph = BooleanArray(2000001)

fun combination(result: Int, idx: Int, n: Int){

    graph[result] = true

    for(i in idx until n){
        if(visited[i]) continue
        visited[i] = true
        combination(result+input[i], i+1, n)
        visited[i] = false
    }
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val n = getInt()
    input = getIntGraph()

    //solve
    combination(0,0,n)

    //output
    for(i in graph.indices){
        if(!graph[i]) {
            write("$i")
            close()
            return
        }
    }

    close()
}