https://www.acmicpc.net/problem/2407

조합의 수를 구하는 간단한 문제이다.
itertools의 combination 연산을 쓰면 시간이 너무 오래걸리므로 $nCm = \frac{n!}{(n-m)!\space r!}$ 공식을 사용한다.

1차 시도

import sys
n, m = map(int, sys.stdin.readline().split())
answer = 1
for _ in range(m):
    answer *= n
    n -= 1
for i in range(2, m+1):
    answer /= i
print(int(answer))

평소 하던대로 곱, 나누기 연산을 작성하였고 나눗셈연산을 하면 float형을 반환하기에 int형으로 변환해서 출력하였다. 테스트케이스를 통과했지만 결과는 실패.
그 이유는 공식문서에서 찾았다.
https://docs.python.org/3/tutorial/floatingpoint.html
Python3 에서 기본적으로 / 연산자는 부동소수점 나눗셈을 한다.
그래서 무의식적으로 int() 함수를 사용하여 형변환을 해줬던 것인데, 그 과정에서 소숫점 오차가 생긴다면 결과값이 달라질 수 있는것이다.

2차 시도

import sys
n, m = map(int, sys.stdin.readline().split())
answer = 1
for _ in range(m):
    answer *= n
    n -= 1
for i in range(2, m+1):
    answer //= i
print(answer)

/ 이 아닌 // 을 통해 몫연산을 수행했더니 통과 되었다.
아! 파이썬에서 정수 나눗셈을 구할 때는 // 연산을 써야 하는구나~

그런데 궁금증이 생겼음
위에서 combination을 구하는 공식은 항상 소수점이 아니라 자연수로 나누어 떨어질텐데 왜 부동소수점 오차가 생긴다는거지?

그래서 실험해봤음

print(10000000000000000000000000000 / 2)
print(int(10000000000000000000000000000 / 2))
# 5e+27
# 4999999999999999791559868416

1e+29를 2로 나누면 5e+27이 나오는게 맞는데
5e+27은 5000000000000000000000000000 이 아닌가? 그런데 이를 int형으로 type casting 했더니 이상한 숫자가 출력되었다.

print(bin(int(10000000000000000000000000000 / 2)))
print(bin(5000000000000000000000000000))

# 0b100000010011111100111001011110001111100010010100000010000000000000000000000000000000000000000
# 0b100000010011111100111001011110001111100010010100000010011000010001000000000000000000000000000

그래서 부동소수점 나눗셈 결과로 나온 5e+27값과 실제 5e+27값을 binary 형태로 찍어보았는데 위와 같은 결과가 나왔다.
어느 지점까지는 동일한 bit가 나오다가 일점 시점 부터는 부동소수점 결과로 나온 값이 0으로 고정되어 버린다는 사실을 알게 되었다.

부동 소수점이란 소수점의 위치를 변경할 수 있기 때문에 제한된 크기의 메모리 공간에서 표현할 수 있는 수의 범위를 키우기 위해 사용하며 그 대신 정확도가 떨어질 수 있다고 한다.
그래서 일정 메모리 이상 사용하게 되면 나누어 떨어지는 연산이라도 소수점 뒷부분이 제대로 계산되지 않고 0으로 채워지는 것 같다고 분석하였다.

그래서 검증을 해보았다.
내 가설대로 일정 메모리 이상 사용하게 되었을 때 소수점 자리수가 무시되는 거라면 나누어지는 숫자를 작게 설정하면 제대로된 결과가 나오지 않을까?

print(int(1000000000 / 2))
# 500000000

음.. 잘 되는것 같다.
그냥 몫을 구하는 나눗셈을 할 때에는 // 연산을 사용하자.

+) 추가로 알게된 점
파이썬에서 / 연산은 부동소수점 연산이므로 a / b 가 수행될 때에는 a 와 b가 float형으로 type casting 된 후 연산이 진행된다고 한다.

print(int(float(10000000000000000000000000000)))
# 9999999999999999583119736832

너무 큰 수는 두 차례의 typecasting을 거쳤을 때 제대로 변환이 안되는 것을 알 수 있다.
왜 이런 현상이 일어나는지에 대해서는 아직 자세하게 조사하지 못했지만 위의 내 가설에 의해 다시한번 확인해 보면

print(bin(int(float(10000000000000000000000000000))))
print(bin(10000000000000000000000000000))
# 0b1000000100111111001110010111100011111000100101000000100000000000000000000000000000000000000000
# 0b1000000100111111001110010111100011111000100101000000100110000100010000000000000000000000000000

처럼 typecasting을 거치고 나면 binary 값이 깨지는 것을 확인하였다.