백준 16400번: 소수 화폐

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

문제 풀이

DP

$dp[i] = i$를 소수의 합으로 나타낼 수 있는 경우의 수

$isPrime[i] = i$가 소수인지 여부

$dp[i] = \sum dp[i - prime]$ $(prime$은 $i$보다 작은 소수$)$

$2$부터 $n$까지 반복하며 소수 $i$를 찾음

찾으면 $i$의 배수는 소수가 아니므로 $isPrime$값 변경

$i$를 $i$ 하나로 나타낼 수 있기 때문에 $dp[i]$를 $1$ 증가

그 뒤에 $j$를 $i + 1$부터 $n$까지 반복하며 $j$를 소수의 합으로 나타내며 마지막에 $i$를 더하는 경우의 수 $dp[j - i]$를 $dp[j]$에 더해줌

$dp[n]$을 출력하면 정답

풀이 설명

소수나라는 특이하게 모든 소수(prime number)를 화폐 단위로 사용한다. 가격이 N인 물건을 구매하려고 했다. 하지만 상점 주인이 거스름돈이 없어 정확히 N원을 지불해달라고 하였다. 소수나라의 화폐를 이용하여 N원을 정확히 만들 수 있는 방법의 가짓수를 구하여라.

즉, N을 소수의 합으로 나타낼 수 있는 가짓수를 구하는 문제다. 여기서는 더해지는 소수의 순서가 달라도 사용하는 소수의 갯수가 같으면 같은 경우의 수로 보기 때문에 순서는 상관이 없다.

따라서 소수를 작은 수부터 오름차순으로 정렬해 나타낸다고 생각하고 예시인 8을 나타내는 경우의 수를 확인하면

1. 2 + 2 + 2 + 2
2. 2 + 3 + 3
3. 3 + 5

이렇게 3가지 경우의 수가 나오게 되고 여기서 마지막 수를 $i$라고 한다면 $8 - i$의 $i$보다 작거나 같은 소수의 합에 $i$를 더하는 형태가 되는 것을 알 수 있다. 따라서 N을 소수의 합으로 나타내는 경우의 수를 구하려면 DP를 활용해 구할 수 있다.

$dp[i]$를 $i$를 소수의 합으로 나타낼 수 있는 경우의 수로 정의한다. 또한 소수를 판별하기 위해 $isPrime[i]$를 $i$가 소수인지 여부로 정의한다. $2$부터 $N$까지 $i$에 대해 반복하며 $i$가 소수라면 $i$의 배수는 소수가 아니기 때문에 $i$의 배수 $j$에 대해 $isPrime[j]$에 false를 대입해준다.

그 이후 $i$는 $i$ 하나의 합으로 나타낼 수 있기 때문에 $dp[i]$의 값을 1 증가 시켜준다. 그 이후에 $i + 1$부터 $N$까지의 수 $j$에 대해 $dp[j]$에 $j$를 소수의 합으로 나타낸 경우의 수 중 마지막 소수가 $i$인 경우의 수, 즉, $j - i$를 $i$보다 작거나 같은 소수의 합으로 나타내는 경우의 수 $dp[j - i]$를 더해준다.

이를 모든 N보다 작은 소수에 대해 반복하면 $dp[N]$에 N을 소수의 합으로 나타내는 경우의 수가 저장되게 된다. 이를 출력하면 정답이 된다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val dp = IntArray(n + 1)
    val isPrime = BooleanArray(n + 1){true}
    for(i in 2..n){
        if(isPrime[i]){
            for(j in i * i..n step i){
                isPrime[j] = false
            }
            dp[i]++
            for(j in i + 1..n){
                dp[j] = (dp[j] + dp[j - i]) % 123456789
            }
        }
    }
    println(dp[n])
}