글 읽기 - 계산과정에서의 중간 결과값이 항상 정수라는 보장이 있을까요?

wns3645 6년 전 0

처음에는 n * n-1 * ... * n-k+1 과 1 * 2 * 3 * ... * k 를 각각 계산해서 답을 구해보려했는데 아무래도 변수 자료형의 제한 때문인지 계산이 불가능하더라구요. 그래서 결국 아래의 방법으로 해결했는데 한가지 의문점이 남습니다.

계산 과정에서 도출 되는 중간 결과 값이 항상 정수 결과 값만 가진다라는 확신을 어떤 이유에서 할 수 있나요? 다시 말해서 ret * (n-k+i) / i 가 항상 정확히 나누어 떨어지는 값이라는걸 어떻게 알 수 있죠?

#include <iostream>

using namespace std;

int main(int argc, char const *argv[]) {


	int n, k;
	while (true)
	{
		cin >> n >> k;
		if(n==0 && k==0)
			return 0;
		if(k > n-k)
			k = n-k;

		long long ret = 1;
		for(int i=1; i<=k; i++)
		{
			ret = ret * (n-k+i) / i;
		}

		cout << ret << endl;
	}

	return 0;
}

yukariko 6년 전 0

i가 증가할때, n-k+i또한 순차적으로 증가합니다.

예를들어 i가 2일땐 곱해지는 숫자도 2개입니다.

n-k+i를 x라고 두면 x * (x + 1) 이고, 이 수는 2의 배수입니다.

오버플로우가 없다면, 2가 아닌 다른 수에 대해서도 같은 이유로 배수가 됩니다.

jh05013 6년 전 0

중간과정에 등장하는 값은 nC0, nC1, nC2, ...입니다.

wns3645 6년 전 0

아 감사합니다. 그리고 중간값이 nC0, nC1, .. 이 되려면 제 코드와는 다르게 ret * (n-i+1)/i 가 되어야 하겠군요. 이렇게 생각하니 훨씬 쉽네요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

계산과정에서의 중간 결과값이 항상 정수라는 보장이 있을까요?

wns3645 6년 전 0

yukariko 6년 전 0

jh05013 6년 전 0

wns3645 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말