[백준,C++] 11050 : 이항계수

 

 

 

문제

---

자연수 N과 정수 K가 주어졌을 때 이항 계수

(N K)

를 구하는 프로그램을 작성하시오.

SMALL

입력

---

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤K ≤N)

반응형

출력

---

 

(N K)

를 출력한다.

 

경우에 따라

우리가 빠르다고 생각하는 방식과 컴퓨터가 빠르다고 생각하는 기준은 다르다

 

우리는 흔히 고딩때 부터 확통을 하면 nCk를 계산 할 때 n!/k!(n-k)!을 활용해 이미 약분 된 공식을 습관화 해서 사용한다

 

그러나 컴퓨터는 이것 보다 파스칼의 삼각형을 이용한 방법을 선호한다

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int pascal(int N, int k) {
	if (k == 0) {
		return 1;
	}
	if (k == 1) {
		return N;
	}
	if (N == k) {
		return 1;
	}
	if (N == k + 1) {
		return N;
	}
	return pascal(N - 1, k) + pascal(N - 1, k - 1);
}

int main() {
	int N;
	int k;

	cin >> N;
	cin >> k;
	
	

	cout << pascal(N,k);
}

 

"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."

위는 파스칼 삼각형의 상부이며

 

이를 통해 우리는 유용한 공식

 

nCk=(nC(k-1)) + ((n-1)C(k-1)) 을 활용해서 재귀 함수를 만들 수 있다

 

재귀 함수의 끝을

 

N이랑 K 가 같으면 1이고

1 차이가 나면 N을 return 하면 된다

 

​

<백준, C++, 10816: 숫자 카드 2>

https://tonnykang.tistory.com/93

[백준,C++] 1920 : 수 찾기