BOJ-1010
21 Jul 2021처음에 틀리고, 질문게시판에 들러 슬쩍 답변을 보았는데 이번 문제는 자료형 문제가 아니라, 조합의 점화식을 이용하고, OVERFLOW가 나지 않도록 유의해야하는 문제라는 답변을 보고 잠깐 고민하다가 수월하게 수정할 수 있었다. 그리고 잘 사용할 줄 몰랐던 <utility> 라이브러리의 pair개념도 적용해보기도 했다. 하핫… 😅
평소에 nCr 조합식을 풀때 접근했던 뇌피셜 방식이 있었는데, 이게 이번 문제 푸는데 많이 도움이 되었다. 만약 조합의 정의만 알고 접근했다면 오버플로우 다루는데에 까다로웠을 법도 하다.
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int comb(int n, int r) {
long long nume = 1, de = 1;
for (int i=r; i>=1; i--) {
nume=nume*n;
n--;
de=de*i;
}
return int(nume/de);
}
int main() {
ios::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int T, N, M;
cin >> T;
vector<pair<int, int>> p, t;
for (int i=0; i<T; i++) {
cin >> N >> M;
pair<int, int> q = make_pair(N,M);
t.emplace_back(q);
}
for (int i=0; i<T; i++) {
pair<int, int> q = (t.back());
t.pop_back();
p.emplace_back(q);
}
for (int i=0; i<T; i++) {
int count = 0;
int n = p.back().second;
int r = p.back().first;
if (0<r<=n && r<=n<30) {
if (n==r) count = 1;
else {
if (r>n/2) r = n-r;
count = comb(n, r);
}
p.pop_back();
cout << count << endl;
}
}
return 0;
}
오랜만에 수학(?) 문제 푸니까 재밌었고, 풀면 풀수록 오기가 생겼는데 그래서 너무 재밌게 풀었다. 간만에 뇌가 말랑해진 것 같은 느낌?!?@ 허허…^_ㅠ! 🧠🧠
