합분해

[baekjoon 2225] 합분해- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건은 N, K가 주어졌을 때 N을 K개의 숫자로 구성하는 경우의 수를 구하는 것이다. 예시로 N이 2이고 K 또한 2이면 경우의 수는 3개로 (0,2), (1,1), (2,0)이다. (0을 포함하고, 1-2, 2-1은 각각 카운트된다.) DP 배열은 2차원 배열로 구성되며, DP[N][K]로 N을 K개로 구성하는 경우의 수를 저장해주었다. 또한 순서가 있는 경우의 수이므로 순열의 경우로 생각해야 하며, 세 자릿수의 순열은 3!이다. 네 자릿수는 4! DP[0][2] ~ DP[N][2]배열엔 각각 2개로 0부터 N까지 구하는 경우..