백준 4811번: 알약

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

문제 풀이

DP

$dp[w][h]$ = 알약 한 조각 전체를 $w$개, 쪼갠 반 조각이 $h$개 있을 때 알약을 먹는 순서의 가지수

$dp[w][h] = dp[w - 1][h + 1] + dp[w][h - 1]$

입력으로 들어오는 $t$에 대해 $dp[t][0]$을 출력하면 정답

풀이 설명

알약이 든 통에서 매일 알약을 꺼낼 때 통에 한 조각 전체가 몇 개 있는지, 쪼갠 반 조각이 몇 개 있는지에 따라 꺼낼 수 있는 가지수가 나뉜다.

예를 들어 첫날에는 통에 쪼갠 반 조각이 없기 때문에 무조건 한 조각을 꺼내게 되고, 그 뒤에는 통에 들어있는 한 조각 전체와 쪼갠 반 조각의 개수에 따라 꺼낼 수 있는 조각이 한 조각 전체일지 쪼갠 반 조각일지 나뉘게 된다.

그리고 꺼낸 알약이 전체 한 조각이라면 반 조각을 쪼개 넣으므로, 어떤 알약을 꺼내는지에 따라 통에 든 알약의 개수가 나뉜다.

$dp[w][h]$를 통에 알약 한 조각 전체가 $w$개, 쪼갠 반 조각이 $h$개 있을 때 알약을 먹는 순서의 가지수라고 정의하고, 이 상태에서 만약 꺼낸 알약이 한 조각 전체라면 통에서 한 조각 전체가 하나 빠지고 꺼낸 알약을 반으로 쪼개서 다시 통에 넣기 때문에 그 이후에 알약을 먹는 순서의 가지수가 $dp[w - 1][h + 1]$이 된다. 만약 꺼낸 알약이 반 조각이라면 그냥 반 조각을 먹기 때문에 그 이후에 알약을 먹는 순서의 가지수는 $dp[w][h - 1]$이 된다.

따라서 점화식이 $dp[w][h] = dp[w - 1][h + 1] + dp[w][h - 1]$이 되게 되고 처음 통에 알약이 30개까지 있을 수 있고, 이 때 30개를 먹을 동안 모두 한조각 전체만 뽑아서 통에 쪼갠 반 조각이 30개가 남을 수 있기 때문에 w, h의 범위도 30까지이다.

이에 따라 dp 테이블에 값을 구하고 문제 조건에 맞게 출력하면 정답이다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val dp = Array(31){ LongArray(31) }
    for(i in 0..30){
        for(j in 0..30){
            if(i == 0){
                dp[i][j] = 1
            } else {
                if(j < 30){
                    dp[i][j] += dp[i - 1][j + 1]
                }
                if(j > 0){
                    dp[i][j] += dp[i][j - 1]
                }
            }
        }
    }
    var t = br.readLine().toInt()
    while(t != 0){
        println(dp[t][0])
        t = br.readLine().toInt()
    }
}