[알고리즘][DP] 2225번 합분해 | baekjoon 문제 풀이

 

https://www.acmicpc.net/problem/2225

2225번: 합분해

 

 

풀이

 

처음에는 직접 경우의 수를 계산해보며 규칙을 찾아내려고 했는데

그려도 감이 안 왔다... 아놔!!!

 

그래서 블로그를 참고하여 규칙을 다시 찾아봤다.

 

 

표를 쓰면서 확인해야 규칙이 잘 보이는구나...

 

어쨌든 이렇게 이전 열의 값과 이전 행의 값을 더하면 현재 값이 된다!

 

arr[i][j] = arr[i - 1][j] + arr[i][j - 1];

 

 

<코드>

#include <iostream>
using namespace std;

int arr[201][201];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int N, K;
	cin >> N >> K; // N은 행, K는 열

	// K가 1일 때, 모든 값은 1
	for (int i = 1; i <= N; i++) {
		arr[i][1] = 1;
	}

	// N이 1일 때, 모든 값은 K
	for (int i = 1; i <= K; i++) {
		arr[1][i] = i;
	}

	for (int i = 2; i <= N; i++) {
		for (int j = 2; j <= K; j++) {
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
			arr[i][j] %= 1000000000;
		}
	}
	cout << arr[N][K];
}