백준 1182 부분수열의 합 Kotlin (완전탐색)

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

1182번: 부분수열의 합

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

풀이

재귀를 이용한 완전 탐색 문제이다.

n이 20일 때 부분집합의 개수는 2^20으로 약 백만 정도이다.

즉 그냥 완전 탐색으로 2^20개의 부분 집합을 검사하면 된다.

뭔가 투 포인터를 써야할 거 같지만, 투 포인터로 구한 답은 부분 집합 중에서 붙어있는 요소들만 구할 수 있기 때문에 답이 되지 않는다.

 

따라서 이 문제는, 그냥 완전 탐색으로 2^20개를 검사하면 되고, 상태 공간 트리를 생각하면 쉽다.

현재 값을 사용할 지, 사용하지 않을 지를  정해주며 탐색하자.

 

코드

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

lateinit var arr: List<Int>
var answer=0

fun dfs(idx: Int, sum: Int, n: Int, s: Int){
    if(idx==n) return
    if(sum+arr[idx]==s) answer++

    dfs(idx+1,sum,n,s)
    dfs(idx+1,sum+arr[idx],n,s)
}

fun main() = with(System.out.bufferedWriter()){

    //input
    val (n,s) = br.readLine().split(' ').map{it.toInt()}
    arr = br.readLine().split(' ').map { it.toInt() }

    //solve
    dfs(0,0,n,s)
    //output
    write("$answer")
    close()
}