jh05013   2년 전

  1. 파이썬처럼 정수 제한이 없는 언어를 제외하면 절대로 nCk를 통째로 구하고 10,007로 나누면 안 됩니다!!! n=1000, k=500일 때 답은 10299보다 크고, 이 값은 unsigned long long의 범위를 훨씬 뛰어넘기 때문에, 따로 자료구조를 만들지 않는 한 답을 저장하는 것 자체가 불가능합니다. 그러니 분자와 분모가 unsigned long long의 범위를 뛰어넘는 건 말할 것도 없습니다.
  2. 그럼 double은 범위가 넓으니까 double로 답을 구할 수 있을까요? 아니요, 구할 수 없습니다. 부동소수점 자료형은 넓은 범위의 수를 표현하기 위해 정확도를 희생한 자료형입니다. 범위도 넓은데 정확하기도 하고 빠르기까지 하면 그건 환상의 자료형이죠.
  3. 그렇다고 분자를 먼저 10,007로 나눈 나머지를 구한 다음에 그 값을 분모로 나눠도 안 됩니다. (a+b)%m = (a%m + b%m)%m, (a*b)%m = ((a%m) * (b%m))%m이지만 (a/b)%m = ((a%m) / (b%m))%m은 아닙니다. 이 문제를 어떻게 풀어야 정답인지는 이 글에서 따로 설명하지 않겠습니다.
  4. 답을 (a%m + b%m)으로 출력하면 틀릴 수 있습니다. 그 값을 다시 m으로 나눈 나머지를 출력해야 합니다.
  5. K=0일 때 답은 1입니다.

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