[C++] 백준 1010번 : 다리 놓기

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

1010번: 다리 놓기

---

 문제 풀이

간단한 이항정리 문제이다.

이항 정리만 이해하고 있으면 쉽게 풀 수 있다.

 함수 Solution

이항 정리를 구현한 함수이다! 값의 범위가 크므로 long long으로 선언해준다.

 느낀 점

솔직히 처음에는 당황해서 생각해내는데 오래 걸렸다. 구글링을 통해서 참고를 해보니 동적 계획법으로 푸는 분들이 많았는데 DP로 풀라는 의도가 아닌 것 같아서 간단하게 풀어보았다.

 코드

#include <iostream>

using namespace std;

int t, n, m;

long long solution(int n, int m) {
	long long ans = 1;
	int r = 1;
	for (int i = m; i > m - n;i--) {
		ans *= i;
		ans /= r++;
	}
	return ans;
}

int main() {
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n >> m;
		cout << solution(n, m) << "\n";
	}
}