백준 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

문제풀이

사용한 알고리즘 : DP

(0) 생각

 멱수의 합은 오름차순으로 표시되어야 한다고 생각해주었습니다.

 즉, 1+1+2+4 = 1+4+2+1 = 4+1+2+1 = ... 입니다.

(1) 코드 10~11

 'dp[x][k] : 2^k 으로 끝나는 x의 멱수 합 개수' 라고 설정해주었습니다.

 문제에서 N의 범위를 10^6 으로 주었으므로, 2^20 까지만 생각해주면 됩니다.

 구하고자 하는 답은 dp[N][0~20]의 합일 것입니다.

 ( 즉, 1로 끝나는 멱수 합 개수 ~ 2^20으로 끝나는 멱수 합 개수)

(2) 코드 17~33

 오름 차순이어야 함을 생각해주면서 dp값을 채웠습니다.

 

 예를 들어 7의 경우

 dp[7][0] : 2^0 로 끝나는 7의 합 개수 = 1개

          = 1+1+1+1+1+1+1

 dp[7][1] : 2^1 로 끝나는 7의 합 개수 = dp[7-2^1][0] + dp[7-2^1][1]

          = 2^0로 끝나는 5의 합 개수 + 2^1로 끝나는 5의 합 개수 = 1+2 = 3개

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

 dp[7][2] : 2^2 로 끝나는 7의 합 개수 = dp[7-2^2][0] + dp[7-2^2][1] + dp[7-2^2][2] 

          = 2^0로 끝나는 3의 합 개수 + 2^1로 끝나는 3의 합 개수 + 2^2로 끝나는 3의 합 개수

          = 1 + 1 + 0 = 2개 

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

 입니다.

(3) 코드 35~36

 구하고자 하는 답은 dp[N][0] + dp[N][1] + ... + dp[N][20] 입니다.