백준 - 부분수열의 합 14225번

코드🔍

import java.io.BufferedReader
import java.io.InputStreamReader

lateinit var arr: IntArray
val visited: BooleanArray = BooleanArray(100000*20+1)

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val total = br.readLine().toInt()

    arr = IntArray(total)

    val inputs = br.readLine().split(" ").map { it.toInt() }
    for ((index, value) in inputs.withIndex()) {
        arr[index] = value
        visited[value] = true
    }

    dfs(0,0)

    for (i in 1..visited.lastIndex) {
        if (!visited[i]) {
            println(i)
            return
        }
    }

}

fun dfs(depth : Int, sum: Int) {
    for (i in depth..arr.lastIndex) {
        val num = arr[i] + sum
        visited[num] = true
        dfs(i+1,num)
    }
}

접근 방법💡

1. 배열 선언:

   • arr: 값들을 저장할 배열로, 크기가 나중에 결정되기에 lateinit var로 선언하였습니다.
   • visited: 합계 값을 추적하기 위한 boolean 배열로, 최대 가능 숫자(20 * 100000)를 기준으로 크기를 설정하였습니다.

2. 입력 처리:

   • 입력값을 읽고 더 쉽게 다룰 수 있는 형태로 변환하여 arr 배열에 저장합니다.

3. 깊이 우선 탐색(DFS):

   • 모든 가능한 합계를 탐색하기 위해 dfs 함수를 구현합니다.
   • 각 방문한 합계를 visited 배열에 표시합니다. 이미 방문한 곳은 건너 뛰기 위해 depth+1을 해주어 다음 단계를 진행하였습니다.

4. 정답 찾기:

   • visited 배열을 순회합니다.
   • 방문하지 않은 첫 번째 인덱스(visited[i] == false)는 주어진 숫자들로 만들 수 없는 가장 작은 합계를 나타냅니다.

출처 : 백준 - 부분수열의 합 14225번