#2225: 합분해

백준 2225번: 합분해

문제:

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

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

입력:

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

풀이:

• 이 문제는 합이 n이 될 때의 모든 경우의 수를 구해주어야 되는 문제이다. 따라서 dp 배열에 경우의 수를 저장 해주면 된다. 2차원 배열로 길이 1과 정수 개수가 1인 경우부터 길이 N과 정수 개수가 K인 경우까지 모든 경우의 수를 구하여 배열에 저장 한 뒤 마지막에 길이 N일 때와 정수 K일 때를 출력 해주면 된다.
• 이 문제는 푸는 방법이 두가지인데 결국에는 똑같은 방식인데 결국은 똑같은 이유에서 파생 된 방식이다. 아래 그림을 보면 두가지 방식으로 볼 수 있다. n = 2, k = 3인 경우를 보면
  1. n=1, k =3인 경우 + n=2, k=2인 경우로 볼 수 있다([n-1, k] + [n, k-1])
  2. k가 2인 경우의 수를 n이 2일때까지 모두 합한 것으로 볼 수 있다 (sum(k=2) until n)

  두가지 중 어떤 방식을 사용하던 상관 없다. 하지만, 두번째 경우는 for문을 한번 써야 되어 n의 값이 크면 시간이 걸릴 수 있다. 첫번째 경우는 배열을 k가 1일 때뿐만 아니라 n인 경우에도 모두 초기화 해줘야 된다는 단점이 있다.

• 두 방식 모두 2차원 배열을 생성 해줘야 되며 배열을 초기화 해준 뒤 이중 for문으로 모든 배열의 값을 바텀업 방식으로 원하는 방식으로 기록 해주면 된다.

방식에 따른 시간 및 메모리 사용량

| 방식 | 메모리(KB) | 시간(ms) | | — | — | — | | 첫번째 방(for문 미사용) | 2052 | 0 | | 두번째 방식(for문 사용) | 2052 | 12 |

• for문을 한번 더 들어가기 때문에 시간이 추가로 늘어난 것을 확인할 수 있다.

코드(첫번째 방식 - for문 미사용):

#include <iostream>
using namespace std;

int n, k;
	
int main(){
	//입력
	cin >> n >> k;
	//k * n 크기를 가진 2차원 배열 생성
	int dp[k+1][n+1]={}; //0번째 모든 배열 0으로 만들기 위해 모든 값 0으로 초기화
	for(int i = 0; i <= n; i++) dp[1][i] = 1; //숫자가 1인 경우의 수는 자기 자신 한개이므로 1로 초기화
	for(int i = 0; i <= k; i++) dp[i][1] = i; //합이 1인 경우는 0 여러개와 1로 이루어지므로 배열의 인덱스로 초기화
	//2차원 배열을 모두 확인
	for(int i = 2; i <= k; i++){
		for(int j = 2; j <= n; j++){
			//합은 같지만 개수가 1이 적은 경우의 수 + 합이 1적지만 개수가 같은 경우의 수
			dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000000;
		}
	}
	//출력
	cout <<dp[k][n];
}

코드(두번째 방식 - for문 사용):

#include <iostream>
using namespace std;

int main(){
	int n, k;
	//입력
	cin >> n >> k;
	//k * n 크기를 가진 2차원 배열 생성
	int dp[k+1][n+1]={}; //0번째 모든 배열 0으로 만들기 위해 모든 값 0으로 초기화
	for(int i = 0; i <= n; i++) dp[1][i] = 1; 
	//2개인 경우의 부터 k개인 경우까지 모든 경우의 수 배열에 저장
	for(int i = 2; i <= k; i++){
		//합이 1인 경우부터 n인 경우까지 모든 경우의 수 배열에 저장
		for(int j = 1; j <= n; j++){
			//현재 배열은 정수 개수가 한개 적을 때의 1부터 현재 값까지의 합 +1 이다
			for(int l = 1; l <=j; l++){
				dp[i][j]=(dp[i][j]+dp[i-1][l])%1000000000;
			}
			//위에서 말한 +1
			dp[i][j]++;
		}
	}
	//출력
	cout <<dp[k][n];
}