백준 2591번: 숫자카드

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

문제 풀이

DP

$dp[i] = i$번째 숫자까지 $1$부터 $34$까지의 카드로 만들 수 있는 가짓수

$dp[i] = dp[i - 1]$ $(num[i - 1] * 10 + num[i] > 34$ $and$ $num[i] \neq 0)$

$dp[i] = dp[i - 2]$ $(num[i] = 0$ $and$ $num[i - 1] \neq 0$ $and$ $num[i - 1] * 10 + num[i] <= 34)$

$dp[i] = dp[i - 1] + dp[i - 2]$ $(num[i] \neq 0$ $and$ $num[i - 1] \neq 0$ $and$ $num[i - 1] * 10 + num[i] <= 34)$

점화식대로 $dp$ 테이블을 구하고 $dp[숫자$ $자릿수]$를 출력하면 정답

풀이 설명

나열되어 있는 숫자를 1부터 34까지의 카드로 만들 수 있는 가지수를 구할 때 이 숫자를 두 부분으로 나누면 마지막 숫자와 나머지로 나눌 수 있다. 하지만 여기서 마지막 숫자와 그 앞의 숫자를 합쳐 두 자릿수를 만들었을 때 카드로 나타낼 수 있는 수가 될 수 있기 때문에 이 때도 확인을 해야 한다.

따라서 dp[i]를 $i$번째 숫자까지 $1$부터 $34$까지의 카드로 만들 수 있는 가짓수라고 정의하면 다음과 같은 경우의 수로 나눌 수 있다.

$dp[i] = dp[i - 1]$ $(num[i - 1] * 10 + num[i] > 34$ $and$ $num[i] \neq 0)$

이 경우는 마지막 $i$ 번째 수가 카드로 나타낼 수 있고 앞의 숫자를 합쳤을 때 카드로 나타낼 수 없을 경우다. $i$ 번째 수가 $0$인지 아닌지 확인해야 하는 이유는 사용할 수 있는 카드 중 $10, 20, 30$이 있기 때문에 나열된 숫자에서 $0$이 나올 수 있기 때문이다

$dp[i] = dp[i - 2]$ $(num[i] = 0$ $and$ $num[i - 1] \neq 0$ $and$ $num[i - 1] * 10 + num[i] <= 34)$

이 경우는 $i$ 번째 숫자가 $0$인 경우이고 이 경우는 카드로 나타내려면 무조건 $10, 20, 30$중 하나일 것이다.

$dp[i] = dp[i - 1] + dp[i - 2]$ $(num[i] \neq 0$ $and$ $num[i - 1] \neq 0$ $and$ $num[i - 1] * 10 + num[i] <= 34)$

이 경우는 $i$ 번째 숫자가 $0$이 아니고 $i - 1$ 번째 숫자도 $0$이 아닐 때 두 숫자를 합쳐서 카드로 나타낼 수 있는 경우이다. 이때도 마찬가지로 $10, 20, 30$이 적힌 카드가 있기 때문에 $i - 1$ 번째 숫자도 $0$이 될 수 있고, 이 때 두 숫자를 합친 수가 $10$ 이하가 되므로 $i$ 번째 숫자를 카드로 만들 수 있는 경우의 수를 중복으로 더해 잘못된 값이 나올 수 있으니 확인해야 한다.

이렇게 구한 점화식으로 $dp$ 테이블을 구하면 $dp[숫자$ $자릿수]$에 현재 구하려는 수를 카드로 나타낼 수 있는 가짓수가 저장되기 때문에 이 값을 출력하면 정답이다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val numStr = br.readLine()
    val num = IntArray(numStr.length + 1)
    for(i in 1..numStr.length){
        num[i] = numStr[i - 1] - '0'
    }
    val dp = IntArray(numStr.length + 1){0}
    dp[0] = 1
    dp[1] = 1
    for(i in 2..numStr.length){
        if(num[i] != 0){
            dp[i] += dp[i-1]
        }
        if(num[i-1] > 0 && num[i-1] * 10 + num[i] <= 34){
            dp[i] += dp[i-2]
        }
    }
    println(dp[numStr.length])
}