[백준 2410번] 2의 멱수의 합 풀이
2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 입력으로 주어진 N을 2의 멱수(2^k) 의 조합으로 몇개나 나타낼 수 있는지 구하는 문제이다. 이는 다이나믹 프로그래밍 기법으로 해결할 수 있다. 수를 하나씩 늘려 가능한 2^k 조합을 구해보면, 다음과 같다. N=1 -> 1 N=2 -> 1+1, 2 N=3 -> 1+1+1, 2+1 N=4 -> 1+1+1+1, 2+1+1, 2+2, 4 N=5 -> 1+1+1+1+1, 2+1+1+1, 2+2+1, 4+1 ... N이 홀수일 경우를 살펴보면, N-1의 가능한 조합 끝에 1씩을 더해주어 완성된다. N=3 인 경우, N=2 일 때의 조합 (1+..
2021. 10. 20.