[python] 백준 - 2410. 2의 멱수의 합

🤔문제 해결

• S1 | 다이나믹프로그래밍

• 유사한 문제 

[python] 백준 - 9084. 동전

동전 문제와 다른 점은 동전은 처음부터 사용할 값이 정해져 있지만

이 문제는 N의 크기에 따라 사용할 수 있는 값이 늘어난다.

N이 7이면 1,2,4 이지만 N이 8이면 1,2,4,8 을 사용할 수 있다.

 

💨

 

💻소스 코드

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)


if __name__ == "__main__":
    N0 = int(input())
    solution(N0)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

링크: https://www.acmicpc.net/problem/2410

2410번: 2의 멱수의 합

---

문제

어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다.

예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다.

입력

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

출력

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