글 읽기 - FAQ

jh05013 5년 전 22

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

kawa1lg1rl 4달 전 0

Python을 사용하고 있고 이 문제가 왜 DP로 분류되었는지 정말 궁금했는데 궁금증이 싹 가셨습니다

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