(백준 / 순열) 다리 놓기

문제 요약

조합 문제

• 강 서쪽과 동쪽을 다리로 이으려한다.
• 다리는 교차될 수 없다.
• 서쪽에서 동쪽을 잇는 가지 수는? 서쪽의 site는 모두 다리가 건설되어있어야한다.

원문

솔루션

상태공간

시간복잡도

구현 순서

코드

#include <iostream>
#include <string.h>
using namespace std;
/*
* R은 서쪽 site 개수
* N은 동족 site 개수
* 다리는 교차 할 수 없음
* 1~N까지의 수로 R길이의 순열을 만드는 문제 (nCr)와 같다.
* mm[N][R] : N-1까지 다리를 이었을 때 R개가 남아있을 때의 상태값
*/
int N, R;
int mm[33][33] = { 0, };
// comb : 1~n-1까지의 다리를 1~r-1 사이의 다리들과 연결한 상태.
//		  n번째 서쪽 site를 r~R 사이 동쪽 site와 이음
int comb(int n, int r) {
	/*ans 현재가지 이은 다리 상태에서 앞으로 이을 수 있는 방법 개수
	*/
	int ans = 0, ret=0;
	//1. 서쪽의 남은 site와 동쪽의 남은 site 개수가 같거나 서쪽의 다리를 다 이으면 1 반환(성립)
	//2. 서쪽의 남은 site가 동쪽의 남은 site 개수보다 적으면 0 반환(실패)
	if (R - r == N - n || n == N+1) return 1;
	if (R - r < N - n) return 0;

	for (int curR = r; curR <= R; curR++) {
		if (mm[n+1][curR+1] == 0) ret = comb(n + 1, curR + 1);
		else ret = mm[n+1][curR+1];
		ans += ret;
	}

	mm[n][r] = ans;
	return ans;
}
int main() {
	/*
	* T:테스트 케이스 개수
	* n 현재 테스트 서쪽 site 개수
	* r 현재 테스트 동쪽 site 개수
	*/
	int T, n, r;
	cin >> T;
	while (T--) {
		//초기화
		memset(mm, 0, 33 * 33 * sizeof(int));

		//구현
		cin >> N >> R;
		cout << comb(1, 1) << endl;

	}
}

이슈

• 1e9로 나누어 주지 않아 정수 범위를 초과해,,,
  • 자바스크립트와 파이썬에 익숙해지는 바람에 그만,,,