중복조합

🧷 문제 https://www.acmicpc.net/problem/2225 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하는 문제이다. 🛠 풀이 혼자 풀다가 해결하지 못해 다른 사람들의 풀이를 참고했다. 여러 사람들의 풀이를 보니 이 문제는 DP로 푸는 것과 중복조합을 이용해 푸는 두 가지 방법이 존재한다. 1. DP Step 1. 먼저 DP table을 (K x K)의 2차원 테이블로 정의하고, 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 dp[N][K]에 넣어준다. ex) N = 0, K = 2 일 경우 : 0부터 2까지의 정수 1개를 더해 합이 2가 되는 경우의 수이다. 만들 수 있는 경우의 수는 0+0 한 가지 밖에 없을 것이다...