합분해1 [백준] 2225 - 합분해, C++ https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 본 문제는 0 ~ N까지 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제다. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 큰 문제를 작은문제로 나누어 해결할 수 있기 때문에 DP문제이고, d[n][k] = d[n-0][k-1] + d[n-1][k-1] + d[n-2][k-1] + ... + d[n-n][k-1] 으로 점화식을 정의 할 수 있다. Bottom-up 방법을 사용하였고, 미지수가 3개이므로 3중 for문을 사용했다. 사실 DP를 풀기전에 완전탐색을 이용하여 해.. 2020. 1. 13. 이전 1 다음