[백준] 5557. 1학년 (Kotlin)

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

5557번: 1학년

 

 

import java.util.*

val arr = arrayListOf<Int>()
var n = 0
var count = 0

fun main() = with(Scanner(System.`in`)){
    n = nextInt()
    nextLine()

    for(i in 0 until n){
        arr.add(next().toInt())
    }

    find(arr[0],0)

    println(arr)
    println(count)
}

fun find(sum: Int, i: Int){

    // 조건 : 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다.
    if(sum < 0 || sum > 20) return

    // 마지막 결과 도달 시 값이 같다면 count++
    if(i == n-2){
        if(arr.last() == sum) count++
        return
    }

    find(sum+arr[i+1],i+1)
    find(sum-arr[i+1],i+1)
}

처음에는 dfs로 모든 경우의 수를 탐색하였다.

 

하지만 예제 입력 1 처럼 숫자가 11개 일 때에는 구할 수 있었지만 

숫자가 많아지면 시간초과가 발생했다.

 

import java.util.*

val arr = arrayListOf<Int>()
var n = 0
val dp = Array(101){Array(21){0L} } // [x]번째 까지의 수를 사용하여 [y]를 만드는 경우의 수

fun main() = with(Scanner(System.`in`)){
    n = nextInt()
    nextLine()

    for(i in 0 until n){
        arr.add(next().toInt())
    }

    // 맨 처음 원소 초기화
    dp[0][arr[0]] = 1

    // 두번째 수 부터 결과 전 수까지 탐색
    for (i in 1 until n-1) {
        for (j in 0..20) {
            // 탐색하지 않은 경우에만
            if (dp[i-1][j] != 0L) {
                // 조건 : 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다.
                if (j + arr[i] <= 20) dp[i][j + arr[i]] += dp[i-1][j]
                if (j - arr[i] >= 0) dp[i][j - arr[i]] += dp[i-1][j]
            }
        }
    }
    println(dp[n-2][arr[n-1]])
}

그래서 dp를 활용하여

인덱스 x번째 까지의 수를 사용하여 y를 만드는 경우의 수는

어차피 이전 계산 값에서 증가할 뿐이므로 계산하지 않고 더해줌으로써 모든 경우의 수를 구했다.