[BOJ] Q2410 2의 멱수의 합

[BOJ] Q2410 2의 멱수의 합

Question

Language: Python

Difficulty: Silver 1~ Gold 5

해당 문제는 Q2293문제와 유사하다.

단, 숫자를 이루는 타입이 2의 제곱 형태이므로 아래와 같이 타입을 미리 생성해서 화용한다.

types=[2**num for num in range(0,20) if 2**num <1000000]

Solution

def solution():
    dp=[0] * (N+1)
    dp[0]=1
    types=[2**num for num in range(0,20) if 2**num <1000000]

    for type in types:
        for i in range(1,N+1):
            if i-type >=0:
                dp[i]+=dp[i-type]
            dp[i]%=1000000000
    return dp[N]

if __name__ == "__main__":
    N=int(input())
    print(solution())