wns3645   2년 전

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

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


yukariko   2년 전

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

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

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

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


jh05013   2년 전

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

wns3645   2년 전

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

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