백준[1182] - 부분수열의 합 (Kotlin)

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val (N, S) = br.readLine().split(" ").map { it.toInt() }
    val nums = arrayListOf<Int>()
    br.readLine().split(" ").map { nums.add(it.toInt()) }
    var count = 0
    
    // 진 부분수열만 포함하므로 S==0일 때 공집합을 제외하기 위해 count - 1
    if (S == 0) count--

    fun dfs(k: Int, value: Int) {
        if (k == N) {
            if (value == S) count++
        } else {
            // 해당 값을 포함하는 모든 부분수열
            dfs(k+1, value)
            
            // 해당 값을 포함하지 않는 모든 부분수열
            dfs(k+1, value + nums[k])
        }
    }

    dfs(0, 0)
    bw.write("$count")
    bw.flush()
    bw.close()
    br.close()
}

 

부분 수열이므로 각 값마다 포함될 때 / 포함되지 않을 때를 구분지어 재귀함수 호출한 완전탐색 

진 부분수열 (공집합을 포함하지 않는 부분수열) 이 조건이므로 S=0일 때 공집합의 경우를 제외하기 위한 count--

 

 

 

고찰 : 아직은 고찰이라 할 게 없따. PS를 이제 막 시작해서 백트래킹부터 천천히 익혀나가보자.

걸린 시간 : -

난이도 : 실버 2

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

1182번: 부분수열의 합