[C++] 백준 1010 - 다리 놓기(정수론 및 조합론)

0. [c++] 백준 1010 - 다리 놓기

 

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

 

1. 풀이

cache[a][b] = a개의 출발점에서 b개의 도착점을 활용해 다리를 만들었을 때 가능한 경우의 수

 

cache[a][b] = cache[a-1][1] + cache[a-1][2] + ... + cache[a-1][b-1] 의 점화식 활용하여 문제 해결

2. 소스코드

#include<iostream>
   
using namespace std;

int N, M, T;

int main() {
	cin >> T;
	while (T--) {
		cin >> N >> M;
		int cache[30][30] = { 0 };
		//출발점이 1개인 경우, 강 반대편 개수에 대응되는 경우의 수
		for (int b_num = 1; b_num <= M; b_num++)
			cache[1][b_num] = b_num;
		
		//출발점이 2~N개일 때, 강 반대편 개수에 대응되는 경우의 수
		for (int a_num = 2; a_num <= N; a_num++)
			for (int b_num = a_num; b_num <= M; b_num++)
				for (int k = 1; k < b_num; k++)
					cache[a_num][b_num] += cache[a_num - 1][k];
		
		cout << cache[N][M] << endl;
	}

	return 0;
}

 

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!