[백준] 1010 다리 놓기 - C

 

 

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

 

---

 

조합공식을 사용하여 간단히 풀면 될 것 같다.

 

조합을 재귀로 표현하기 위해 관련된 수식들을 좀 찾아보았다.

nCn = 1, nC0 = 1, nCr = n-1Cr + n-1Cr-1 라고 한다.

앞의 두 식을 기저조건으로 잡고 뒤의 식을 점화식으로 잡으면 될 것 같다.

 

#include <stdio.h>

int memo[35][35];

int combination(int n, int r) {

	if (n == r || r == 0) {
		memo[n][r] = 1;
		return memo[n][r];
	}

	if (memo[n][r]) {
		return memo[n][r];
	}
	else {
		memo[n][r] = combination(n - 1, r) + combination(n - 1, r - 1);
		return memo[n][r];
	}
}

int main() {
	
	int t;
	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		int n, r;
		scanf("%d %d", &r, &n);
		printf("%d\n", combination(n,r));
	}

	return 0;
}

 

 

일반적인 재귀를 사용하면 시간이 부족 할 수 있기 때문에 메모이제이션을 사용했다.

 

---