백준 2410번: 2의 멱수의 합

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

문제 풀이

DP

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

$dp[i] = dp[i - 1] + dp[i / 2]$ ($i$가 짝수일때)

$dp[i] = dp[i - 1]$ ($i$가 홀수일때)

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

풀이 설명

자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구해야 하고, 2의 멱수는 $2^k$로 표현되는 자연수를 의미한다.

예시로 든 7을 2의 멱수의 합으로 나타내는 경우를 살펴보면

1. 1+1+1+1+1+1+1
2. 1+1+1+1+1+2
3. 1+1+1+2+2
4. 1+1+1+4
5. 1+2+2+2
6. 1+2+4

이렇게 되고 여기서 앞의 1을 제거해보면 다음과 같이 6을 2의 멱수의 합으로 나타내는 경우가 된다는 것을 알 수 있다.

1. 1+1+1+1+1+1
2. 1+1+1+1+2
3. 1+1+2+2
4. 1+1+4
5. 2+2+2
6. 2+4

여기서 1번부터 4번까지는 합에 1이 포함이 되고, 5번과 6번은 포함되지 않는 것을 알 수 있다. 1번부터 4번까지는 5를 2의 멱수의 합으로 나타내는 경우에 1을 더한 것이고, 5번과 6번은 3을 2의 멱수의 합으로 나타낸 것을 2배한 것과 같다.

2의 멱수가 1을 제외하면 항상 짝수이기 때문에 홀수를 나타내려면 항상 1을 가지고 있어야 한다. 그리고 1을 포함하는 2의 멱수의 합은 그 값보다 1 작은 값의 2의 멱수의 합에 1을 더하는 경우이고, 1을 포함하지 않는 2의 멱수의 합은 그 값을 2로 나눈 값의 2의 멱수의 합에 2배를 한 경우와 같다.

따라서, 홀수의 경우는 항상 1을 가지고 있어야 하기 때문에 2의 멱수의 합으로 나타내는 경우의 수가 그 값보다 1 작은 값을 2의 멱수의 합으로 나타내는 경우의 수와 같아진다.

짝수의 경우에는 그 값보다 1 작은 값을 2의 멱수의 합으로 나타내는 경우의 수와 그 값을 절반으로 나눈 값을 2의 멱수의 합으로 나타내는 경우의 수를 더한 값이 된다.

이를 점화식으로 나타내면

$dp[i] = dp[i - 1] + dp[i / 2]$ ($i$가 짝수일때)

$dp[i] = dp[i - 1]$ ($i$가 홀수일때)

가 된다.

이에 따라 dp 배열을 구해 dp[n]을 출력해주면 정답이 된다.

소스 코드

fun main(){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().toInt()
    val dp = IntArray(n + 1)
    dp[1] = 1
    for(i in 2..n){
        if(i % 2 == 0){
            dp[i] = dp[i - 1] + dp[i / 2]
        } else {
            dp[i] = dp[i - 1]
        }
        dp[i] %= 1000000000
    }
    println(dp[n])
}