처음에는 단순히 조합의 값을 구해 10007로 나눈 나머지를 찾는 문제라고 생각하고 접근했다. 처음 풀이는 단순히 K가 0인 경우와 N과 K의 값이 같은 경우는 조합에서 특수한 경우이므로 먼저 걸러주기 위해 조건식을 달아주었고, 그 이외의 조건에서 조합의 값을 구하는 방식이었다.(이후의 풀이에서도 K가 0인 경우, N과 K의 값이 같은 경우를 걸러내는 코드는 살려두고 진행했다.) 아래는 그 코드이다.
def factorial(num):
if num == 1:
return 1
else:
return num * factorial(num - 1)
def main():
N, K = map(int, input().split())
if K == 0:
combination = 1
elif N == K:
combination = 1
else:
combination = factorial(N) / (factorial(N-K) * factorial(K))
print(int(combination % 10007))
if __name__ == "__main__":
main()결과는 런타임 에러 중에서도 Recursion Error였다. 알아보니 이는 백준 채점 기준 중 최대 recursion의 횟수가 1000으로 고정되어있기 때문이었다. 내 코드상에서는 입력이 999만 들어오더라도 횟수를 꽉 채워버리는 상황이 발생한다. 이를 해결하기 위해 단순 반복문으로 코드를 변경하였다. 아래가 그 첫번째 코드이다.
def main():
N, K = map(int, input().split())
factorial_N_K = 1
factorial_K = 1
if K == 0:
combination = 1
elif N == K:
combination = 1
else:
for _ in range(K):
factorial_N_K *= N
N -= 1
factorial_K *= K
K -= 1
combination = factorial_N_K / factorial_K
print(int(combination % 10007))
if __name__ == "__main__":
main()이 코드는 그냥 틀렸다는 결과가 나왔다. 뭐가 문제일까를 알지 못하겠어서 문제의 질문 검색탭에 들어가보았다. 나와 비슷하게 코드를 짜신 분이 올린 질문을 발견했는데, 해결책이 combination = factorial_N_K / factorial_K => combination = factorial_N_K // factorial_K 라는 조금 머리가 띵한 사실을 알게 되었다...
어떻게 된 일일까?
이유는 숫자 자체가 매우 크기 때문인 것 같았다. 숫자 자체가 매우 클 때 /을 통해 값을 얻은 것과 //을 이용해 값을 얻은 예를 보여주겠다.
/과 //를 사용해 1000과 500의 이항계수를 구한 값의 차이이다. //의 경우 값을 끝까지 구해준다. 반면 /의 경우 값을 중간에 끊고 e+299라는 exponential의 형식으로 값을 구한다. 이는 e앞까지의 숫자에 10의 299승을 했다는 뜻이다. 이렇게 큰 숫자에서 10의 299승을 곱하기 전까지의 숫자(무려 299개...) 뒤를 다 날려버린다면, 다음 계산 결과에 지대한 영향을 끼칠 것이다. 그에 10007을 나눈 나머지의 결과가 아래 두 줄인데, 값의 차이가 많이 나는 것을 알 수 있다. 아래는 제출 후 채점 결과가 정답이었던 코드이다.
def main():
N, K = map(int, input().split())
factorial_N_K = 1
factorial_K = 1
if K == 0:
combination = 1
elif N == K:
combination = 1
else:
for _ in range(K):
factorial_N_K *= N
N -= 1
factorial_K *= K
K -= 1
combination = factorial_N_K // factorial_K
print(int(combination % 10007))
if __name__ == "__main__":
main()이때까지는 /과 //를 단순히 몫을 구하냐 아니냐의 차이로만 생각했는데, 내가 다루는 수가 어느정도냐(목적)에 따라 적절히 선택하여 쓸 수 있어야 한다는 사실을 알게된 기회였다.
