[백준 / BOJ] 2410 2의 멱수의 합

문제

출처 : www.acmicpc.net/problem/2410

2410번: 2의 멱수의 합

자연수 N을 입력받았을때, 그 자연수를 2의 멱수의 합으로 나타내는 경우의수를 구하시오

예를들어 

3 

1 + 1 + 1

1 + 2

두가지 경우로 나타낼수있다.

풀이

www.acmicpc.net/problem/2293

2293번: 동전 1

입력받은 동전들을 이용해 숫자 K를 만드는 동전 1이랑 똑같은 문제였다.

 

점화식은 동전과 같다.

 

i = 1 부터 N까지 2의 멱수들을 가지고 만들수있는 경우의수 를 i*2씩 늘려가며 봐줬다.

 

2의 멱수가 1 일때와 2일때 각각 배열에 채워넣는 순서는 다음과 같다.

 

우선 i가 1일때, 1만 사용해서 만들수있는 경우의수는 한가지이다.

0 = 0

1 = 1 

2 = 1 + 1

3 = 1 + 1 + 1

.

.

.

2는 1이 갖고있는 조합에 1을 더하면 나오고, 3은 2가 갖고있는 조합에 1을 더하면 된다.

 

다음 i = 2 일때, 1과 2를 사용해서 만들수있는 경우의수는 다음과 같다.

0 = 0

1 = 1

2 = 1 + 1 , 2

3 = 1 + 1 + 1 , 1 + 2

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

.

.

.

만들려는 수가 N보다 작다면 봐줄필요가없다. 0과 1은 2보다 작으니 봐주지않고, 2부터 봐줬다.

0이 갖고있는 조합에다가 2를 더해주면 2가 만들어진다.

마찬가지로 1이 갖고있는 조합에 +2를 하면 3이 만들어진다.

 

i*2 = 4일때, 1,2,4를 이용해서 만들수있는 수는

0 = 0

1 = 1

2 = 1 + 1 , 2

3 = 1 + 1 + 1 , 1 + 2

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

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

.

.

.

4와 5 또한 마찬가지로

0과 1이 갖고있는 조합에 4를 더해주면 각각의 수가 만들어지는걸 볼수있다.

 

따라서 dp에 각각 2의멱수를 갖고 수를 만들수있는 조합의 수가 저장되어있다면, 점화식은

dp[만들려는수] = dp[만들려는수] + dp[만들려는수에 i만큼 뺀값]이 된다.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2410%202%EC%9D%98%20%EB%A9%B1%EC%88%98%EC%9D%98%20%ED%95%A9/main.cpp

devxb/JJUNalgo