문제
백준 2225번 - 합분해
아이디어
- dp 배열
dp[n][k]
를 0~n 숫자 중에 k개를 사용하여 n을 만드는 경우의 수라 가정한다.
dp[0][1~k]
는 1로 초기화 할 수 있다. 왜냐하면 합이 0이 되기 위해 0밖에 못 쓰기 때문이다.
dp[0~n][1]
은 1로 초기화 할 수 있다. 왜냐하면 숫자 1개를 사용해서 합이 n이 되기 위해서는 자기 자신만 사용할 수 있다.
- 우선 점화식을 세우기 위한 가정을 세워본다.
- 덧셈의 첫번째 숫자를 0 으로 사용하면 나머지
k-1
개의 숫자로 n
을 만들어야 한다. (dp[n][k-1]
)
- 덧셈의 첫번째 숫자를 1 이상으로 사용하면
k
개의 숫자로 n-1
을 만들 때 식에서 숫자만 변경하면 된다.(dp[n-1][k]
)
- 최종 점화식 :
dp[n][k]
= dp[n][k-1] + dp[n-1][k]
예상 시간 복잡도
코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_2225 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int[][] dp = new int[n + 1][k + 1];
//0으로 합이 0이 되기 위한 경우의 수
for (int i = 1; i <= k; i++) {
dp[0][i] = 1;
}
//숫자 1개로 n을 만드는 경우의 수
for (int i = 0; i <= n; i++) {
dp[i][1] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= k; j++) {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1_000_000_000;
}
}
System.out.println(dp[n][k]);
}
}