[문제]
어떤 자연수 N을 2의 멱수의 합으로 나타내는 경우의 수를 구하는 프로그램을 작성하시오. 2의 멱수라는 것은, 2^k으로 표현되는 자연수를 의미한다.
예를 들어 7을 2의 멱수의 합으로 나타내는 경우의 수는 다음의 여섯 가지가 있다.
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+2+2
1+1+1+4
1+2+2+2
1+2+4
입력
첫째 줄에 N(1≤N≤1,000,000)이 주어진다.
[출력]
첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.
import java.util.Scanner;
public class Main {
private static int dp[][];
private static int MOD = 1000000000;
private static int result = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
dp = new int[n+1][20]; // 0, 0 은안씀
System.out.println(dinamic_programming(n, 19));
/*
* 간단하게 푸는로직
int dp2[] = new int[n+1];
dp2[0] = 1;
dp2[1] = 1;
for(int i = 2 ; i <= n ; i ++)
dp2[i] = (dp2[i-2] + dp2[i/2])%MOD;
System.out.println(dp2[n]);
*/
} //DP 사용
private static int dinamic_programming(int i , int j) {
if(i < 0)
return 0;
if(i == 0)
return 1;
if(i > 0 && j == 0)
return dp[i][0] = 1;
if(dp[i][j] != 0)
return dp[i][j];
int check = i - (int)Math.pow(2 , j);
if (check >= 0) {
return (dp[i][j-1] = dinamic_programming(i, j - 1) % MOD) + (dp[check][j] = dinamic_programming(check, j) % MOD);
}else {
return dp[i][j] = dinamic_programming(i , j-1) % MOD;
}
}
}아주작은단위에서의 값을 미리구하고 작은단위를 쌓아서 구하고자하는 문제를 푸는것이 핵심이다.
먼저 이 코드는 dp[i][j] 를 숫자i를 2^j로 나타내는 경우의 수인것을 참고하여 작성하였다.
따라서 아주 작은단위로는 dp[i][0] 으로, 숫자 i 를 2⁰으로 나타내는경우의수는 무조건 1임을 더해줬고 또한 i= 0 이면 dp[i][j]의 정의에의해
dp[2][19] = dp[2][18] = dp[2][17] … dp[2][1] = dp[2,0] + dp[0,1]; 이되므로 dp[2][1] = 2 를 맞추기위해 i=0 일때 1의값을 리턴한다.
약간 직관적으로 보이지는않으나 문제를 쪼개보면 이게 맞는 과정이다.
사용한 수식은 dp[i][j] = dp[i][j-1] + dp[i-2^j][j]; 를 재귀적으로 반복하는 수식. dp[i][j-1]은 2^j를 사용하지않은경우 그보다작은 2^(j-1)를 재귀적으로호출(dp[i][j-1] = dinamic programming(i, j — 1) % MOD 으로 호출함과동시에 값을 dp에 저장하였다.) , dp[i-2^j][j]는 2^j를 사용하되 i≥2^j 를 충족할때의 조건이다. 이값이 0이거나 크면 dp[i-2^j][j]를 사용.
