BOJ 6591 - 이항 쇼다운

문제

이항 계수 C(n, k)를 구하라.

입력

여러 테스트 케이스에 n과 k가 주어지며, 둘 다 0이면 종료한다.

출력

각 케이스마다 C(n, k)를 출력한다.

예제

입력	출력
`4 2` `0 0`	`6`

풀이

오버플로를 방지하면서 이항 계수를 직접 계산한다.

r = min(k, n-k)로 계산량을 최소화한다
분자를 n부터 내려가며 곱하고, 동시에 분모를 1부터 올라가며 나눈다
곱셈과 나눗셈을 교대로 수행하여 중간 결과의 오버플로를 방지한다

핵심 아이디어: C(n, k) = C(n, n-k) 대칭성으로 반복 횟수를 줄이고, 곱하면서 나누는 방식으로 정수 범위 내에서 정확히 계산한다.

코드

#include <iostream>
using namespace std;
 
void swap(int *a, int *b)
{
  int *temp = a;
  a = b;
  b = temp;
}
 
int main()
{
  while (true)
  {
    int n, k;
    cin >> n >> k;
    if (!n && !k)
      break;
    int r = n - k;
    if (r > k)
      swap(r, k);
 
    int div = 1;
    long long ans = 1;
    for (int i = n; i >= n - r + 1; i--)
    {
      ans *= i;
      ans /= div;
      div++;
    }
 
    cout << ans << '\n';
  }
  return 0;
}

복잡도

시간: O(min(k, n-k))
공간: O(1)

문제

BOJ 6591 - 이항 쇼다운

이항 계수 C(n, k)를 구하라.

입력

여러 테스트 케이스에 n과 k가 주어지며, 둘 다 0이면 종료한다.

출력

각 케이스마다 C(n, k)를 출력한다.

예제

입력	출력
`4 2` `0 0`	`6`

풀이

오버플로를 방지하면서 이항 계수를 직접 계산한다.

r = min(k, n-k)로 계산량을 최소화한다
분자를 n부터 내려가며 곱하고, 동시에 분모를 1부터 올라가며 나눈다
곱셈과 나눗셈을 교대로 수행하여 중간 결과의 오버플로를 방지한다

핵심 아이디어: C(n, k) = C(n, n-k) 대칭성으로 반복 횟수를 줄이고, 곱하면서 나누는 방식으로 정수 범위 내에서 정확히 계산한다.

코드

#include <iostream>
using namespace std;
 
void swap(int *a, int *b)
{
  int *temp = a;
  a = b;
  b = temp;
}
 
int main()
{
  while (true)
  {
    int n, k;
    cin >> n >> k;
    if (!n && !k)
      break;
    int r = n - k;
    if (r > k)
      swap(r, k);
 
    int div = 1;
    long long ans = 1;
    for (int i = n; i >= n - r + 1; i--)
    {
      ans *= i;
      ans /= div;
      div++;
    }
 
    cout << ans << '\n';
  }
  return 0;
}

복잡도

시간: O(min(k, n-k))
공간: O(1)