[백준 / BOJ] 1010번 다리 놓기 (C++, Python)

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

1010번: 다리 놓기

---

문제

---

문제 풀이

고등학생때 확통에서 많이 풀던 유형의 문제다. 이전에 풀었던 조합 문제의 알고리즘을 따오면 된다.

 

C++의 경우에 nCr을 아예 풀어 쓴 공식을 활용한 방법이 있어서 구현해보았다.

 

for (int i = M; i > M - N; --i) {
    res = res * i;
    res = res / tmp++;
}

 

C++ 코드 전문

	#include <algorithm>
	#include <iostream>
	#include <vector>
	void init() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	}
	int main() {
	init();
	int T;
	std::cin >> T;
	for (int t = 0; t < T; ++t) {
	int N, M, res = 1, tmp = 1;
	std::cin >> N >> M;
	for (int i = M; i > M - N; --i) {
	res = res * i;
	res = res / tmp++;
	}
	std::cout << res << "\n";
	}
	return 0;
	}

view raw 1010_다리 놓기 (22.06.12 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	import sys
	import math
	input = sys.stdin.readline
	T = int(input())
	for _ in range(T):
	N, M = map(int, input().split())
	print(math.comb(M, N))

view raw 1010_다리 놓기 (22.06.12 성공).py hosted with ❤ by GitHub

 

소감