Written by java-style
on 2021-09-27

합분해 (2225번) [node.js, JavaScript]

문제 설명

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

의사코드

k가 1이라면 n를 만드는 방법은 모두 1가지씩이다. 예를들면 k가 3, n이 4라면 4를 만들려면 k-1이면서 0부터 n까지 경우의 수를 모두 더하면 됩니다. 즉, k가 2일때 n이 0,1,2,3,4일 때 경우를 생각해보면 쉽게 풀이할 수 있습니다. 0 일때 4를 더하면 되고, 1일때 3을, 2일때 2를, 3일때 1을, 4일때 0을 더하면 정수 4을 만들 수 있기 때문입니다. 정수 k개를 더해서 그 합이 n이 되는 경우의 수를 만드는 점화식은 DP[k][n] = DP[k-1][n-1]+DP[k-1][n-2]+DP[k-1][n-3] ... +DP[k-1][n-n]이 됩니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().split("

"); solution(input); function solution(input) { const [n, k] = input[0] .split(" ") .map(Number); const DP = Array.from({length:k+1},()=> Array.from({length:n+1},()=> 0)); for (let i = 0; i <= n; i++) { DP[1][i] = 1; } for (let i = 2; i <= k; i++) { for (let j = 0; j <= n; j++) { if (j === 0) { DP[i][j] = 1; } else { for (let x = 0; x <=j; x++) { DP[i][j] = (DP[i][j] + DP[i - 1][x]) % 1000000000; } } } } return console.log(DP[k][n]); }

from http://jinblog123.tistory.com/89 by ccl(A) rewrite - 2021-09-27 18:27:05

Top