[백준] 11050번: 이항 계수 1 C++로 풀어보기

11050번 설명

생각

일단 이항 계수가 무슨 뜻인지 몰라서 검색을 해봤다.

이항 계수 뜻 (출처: 위키백과)

이항 계수는 nCk 였구나. 고등학교 확통 시간 때 배운 적이 있다. 문제 조건에서 0 <= K <= N이라고 했으므로 n! / (k!(n-k)!)만 생각하면 된다.

 

팩토리얼을 구해야 되는데, 재귀를 이용하거나 for문을 사용하면 된다. 일단 재귀로 해보고 안되면 for문을 사용해야 겠다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int factorial(int n) { // 팩토리얼 함수
	if (n <= 1) { // n == 1로 하면 안된다!!
		return 1;
	}
	else {
		return n * factorial(n - 1); // 재귀를 사용했다.
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n, k;
	cin >> n >> k;

	int ans = factorial(n) / ( factorial(k) * factorial(n - k) );

	cout << ans;

}

결과

11050번 결과

처음에는 재귀를 사용했는데, if (n <= 1)을 if (n == 1)로 썼다가 시간 초과가 되었고,

그 다음에는 for문을 사용했는데 for문도 시간 초과가 떴다.

제대로 된 재귀를 이용해야 풀 수 있는 문제였다.