[알고리즘] 백준 1010번: 다리 놓기 (C++)

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

1010번: 다리 놓기

다리를 잇는 경우가 고등학생 때 배우던 조합론: 콤비네이션을 기억해낼 수 있다면 풀릴 수 있는 문제였다.

시간도 0.5초로 짧아서 탑 다운 DP형식으로 구현을 했고 범위는 30 이전이라 문자열의 합은 구현하지 않아도 될 거 같았다.

 

콤비네이션에 관한 문제를 예전에 풀고, 포스팅해놓았어서 쉽게 풀렸다.

https://draw-code-boy.tistory.com/101

[알고리즘] 백준 2407번: 조합 (C++), Combination, Permutation

[AC 코드]

#include <iostream>
#include <cmath>
#define MAX 30
using namespace std;

int cache[30][30];
int T;

int combination(int n, int r) {
	if (n == r || r == 0) {
		return 1;
	}
	else {
		if (cache[n][r] != 0) {
			return cache[n][r];
		}
		else {
			return cache[n][r] = combination(n - 1, r - 1) + combination(n - 1, r);
		}
	}
}

int main() {
	cin >> T;
	for (int t = 1; t <= T; t++) {
		int M, N;
		cin >> M >> N;
		cout << combination(N, M) << '\n';
	}

	return 0;
}

---

고등학교 수학책... 꺼내야 할까