[백준/BOJ] 11050번 이항 계수 1 (C/C++)

백준 온라인 저지(BOJ) 11050번 이항 계수 1

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

11050번: 이항 계수 1

* 사용언어 : C언어, C++

 

1. 문제

자연수 N과 정수 K가 주어졌을 때 nCk(이항 계수) 출력

 

2. 풀이

이항 계수 공식을 활용하여 풀 수도 있지만 N과 K의 크기가 작기 때문에 단순하게 구현했습니다.

nCk는 n! / ((n - k)! * k!) 이므로 {n * (n - 1) * ... * (n - k + 1)} / k! 입니다.

 

따라서 n부터 1씩 빼면서 곱하는 절차를 k번 진행한 후, 그 값을 k!로 나눠주면 됩니다.

 

단, 이항 계수는 K가 0이거나 N과 K가 같으면 가능한 경우의 수가 1이므로 결과값이 1입니다.

위 조건에 해당하는 경우 nCk를 구하는 절차를 수행하지 않게 해주었습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11050_이항 계수 1
1112KB	0ms
*/
#include <cstdio>

int N, K, res = 1;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d %d", &N, &K);

	if (K > 0 && N != K) {
		for (int i = 0; i < K; ++i) res *= (N - i);
		while (K) res /= K--;
	}

	printf("%d\n", res);
	return 0;
}