2410

2의 멱수의 합

 

문제

어떤 자연수 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

입력

첫째 줄에 N(1≤N≤1,000,000)이 주어진다.

 

출력

첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.

---

수학적으로 생각하여 재귀를 통해서 2의 제곱수들로 나누어진 수 만큼 분리를 할 수 있다고 생각하여 코드를 짜보았다.

 

N = int(input())
K = N // 2 - 1
count = 1
def sol(N,K):
    global count
    if K <= 0 or N == 0:
        return 0
    while(K):
        print(N,K)
        count += N//(2**K)
        sol(N - (2**K),K - 1)
        K -= 1
    return count

sol(N,K)
print(count)

하지만 이렇게 하니 런타임초과가 나서 알고리즘을 확인해보았더니 DP 문제였다. 재귀말고 해당 방법을 활용하여 풀어 봐야 겠다.

결국 어떻게 식을 세워야할지 모르겟어서 찾아보았다.

N = int(input())

def solution(N):
    nums = [2 ** x for x in range(21)]
    dp = [0] * (N + 1)
    dp[0] = 1
    for num in nums:
        if num <= N:
            for j in range(num, N + 1):
                dp[j] += dp[j - num]
    print(dp[-1] % 1000000000)

말고도 

n = int(input())

dp = [0 for _ in range(n // 2 + 1)]
dp[0] = 1
for i in range(1, n // 2 + 1):
    dp[i] += dp[i - 1]
    dp[i] += dp[i // 2]
    dp[i] %= 1_000_000_000

print(dp[-1])

아무래도 dp는 식 찾는게 진짜 어려운 거 같다.