[BOJ 2691 // C++] 이항 쇼다운

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2691번 문제인 이항 쇼다운이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/6591

6591번: 이항 쇼다운

주어지는 n과 k 값을 받아 입력이 끝날 때까지 이항계수를 계산해나가는 문제이다.

이항계수는 (n부터 하나씩 감소하는 k개의 수의 곱) / (1부터 하나씩 증가하는 k개의 수의 곱)으로 계산할 수 있다.

특히, 연속된 x개의 자연수의 곱에는 x의 배수가 무조건 있으므로 계산 과정에서 소수점이 나오지 않게 식을 만들 수 있다.

 

답안의 크기는 int범위 내이지만 중간 계산과정에서 int의 범위를 넘어설 수 있으므로 ans 변수를 long long으로 지정하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int x, y;
    cin >> x >> y;
    while (x + y != 0) {
        if (y > x - y) y = x - y;
        long long ans = 1;
        for (int i = 1;i <= y;i++) {
            ans *= x;
            ans /= i;
            x--;
        }
        cout << ans << '\n';
        cin >> x >> y;
    }
    return 0;
}