[백준 1010] 다리 놓기 #조합

# 문제 링크

www.acmicpc.net/problem/1010

1010번: 다리 놓기

강 동쪽의 M 개 사이트에서 강 서쪽의 N개 사이트와 연결할 수 있는 경우의 수를 계산하는 문제이다. 중복이 안돼서 조합의 경우의 수를 구해야 한다. 조합 계산을 어떻게 했더라.. 아래와 같은 식을 떠올렸다.

 

조합 계산식

그리고 구현한 코드

 

#include <iostream>
using namespace std;
int main() {
	int T;
	cin >> T;
	while (T--) {
		int N, M;
		cin >> N >> M; // M 개 중에 N 개를 뽑는 조합의 수 
		unsigned long long int sum = 1;
		for (int i = M ; i > M - N ; i--) sum *= i;
		for (int i = N; i > 1; i--) sum /= i;
		cout << sum << '\n' ;
	}
	return 0;
}

 

테스트 코드는 잘 돌아가는데, 왠지 계속 틀렸습니다가 떴다. unsigned long long 보다 더 큰 수가 나오나보다..

 

산술 계산이 안되니 DP로 풀어보았다. 조합의 성질을 참고하였다. (feat. 조합 삼각형)

 

조합의 성질 (출처: 강쌤의 수학 블로그)

 

# 제출 코드

 

#include <iostream>
using namespace std;

long int a[31][31];

int main() {
	int T;
	cin >> T;

	a[1][0] = 1;
	a[1][1] = 1;
	for (int i = 2; i <= 30; i++) {
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) a[i][j] = 1;
			else {
				a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
			}
		}
	}

	while (T--) {
		int N, M;
		cin >> N >> M; // M 개 중에 N 개를 뽑는 조합의 수 
		cout << a[M][N] << '\n';
	}
	return 0;
}

 

간단해보이는 문제였는데도 꽤 시간이 걸렸다.. 정말 PS의 길은 멀고도 험하구나..

 

 

 

# 참고

 

m.blog.naver.com/PostView.nhn?blogId=vollollov&logNo=220947452823&proxyReferer=https:%2F%2Fwww.google.com%2F