[백준/파이썬] 2410번 2의 멱수의 합

http://xn--acmicpc-hu32a.net/problem/2410

 

이 문제를 해결하기 위해 1부터 8까지 다 적어봤다

1 = 1

2 = 1+1, 2

3 = 1+1+1, 2+1

4 = 1+1+1+1, 2+1+1, 2+2, 4

5 = 1+1+1+1+1, 2+1+1+1, 2+2+1, 4+1

6 = 1+1+1+1+1+1, 2+1+1+1+1, 2+2+1+1, 4+1+1, 2+2+2, 4+2

7 = 1+1+1+1+1+1+1, 2+1+1+1+1+1, 2+2+1+1+1, 4+1+1+1, 2+2+2+1, 4+2+1

8 = 1+1+1+1+1+1+1+1, 2+1+1+1+1+1+1, 2+2+1+1+1+1, 4+1+1+1, 2+2+2+1+1, 4+2+1+1, 2+2+2+2, 4+2+2, 4+4, 8

..

 

우선

모든 수는  이전 더하기 값들에 +1한만큼 횟수가 존재한다.

5 = 4의 덧셈 표시에 +1한 값 : (1+1+1+1, 2+1+1, 2+2, 4) +1

=> ( 1+1+1+1+1, 2+1+1+1, 2+2+1, 4+1)

 

단, 짝수인 경우에는 N/2의 덧셈 구조에 *2를 추가해주면 된다.

6 = 5의 덧셈 표시+1한값 , 3( 1+1+1, 2+1 )의 덧셈표시에 *2한값 ( 2+2+2, 4+2 )

 

따라서 식으로 나타내면 i가 홀수인 경우 dp[i]=dp[i-1], i가 짝수인 경우는 dp[i]=dp[i-1]+dp[i//2]이다.

 

import sys
input = sys.stdin.readline
N=int(input())

dp=[0]*(N+1)
dp[1]=1
if N>=2:
    dp[2]=2

for i in range(3,N+1):
    if i%2==0:
        dp[i]=(dp[i-1]+dp[i//2])%1000000000
    else:
        dp[i]=dp[i-1]%1000000000
print(dp[-1])