[Python] 다리 놓기: 나누어 떨어지는 정수 나눗셈의 오차 줄이기

문제 링크

1010번: 다리 놓기

문제 요약

다리 놓기 문제는 서쪽의 N개 사이트와 동쪽의 M개 사이트를 연결하는 다리 N개를 서로 교차하지 않도록 짓고 싶다. N과 M이 (N ≤ M) 주어질 때, 다리 건설이 가능한 모든 경우의 갯수를 출력하시오.

풀이 설명

다리끼리 교차하지 않아야하므로, 답은 M개의 사이트에서 N개를 고르는 경우의 수=combination(range(M), N)의 길이이다. 이전 문제를 풀면서 itertools의 combination을 배웠던터라 무지성으로 신나게 아래와 같은 코드를 제출했다.

print(len(list(combination(range(M), N))))

결과는 시간초과이다.  (제출 번호 71022244)

 

다시 정신 차리고, 경우의 수만 구하는 것이니 조합 식으로 M!/(N!*N!)을 계산하여 출력해본다.

처음 시도에서는 / 연산자를 사용하여 답을 계산하고 이를 int()로 출력하였다. (제출번호 71022564)

print(int(bridge_num))

 

 

틀렸습니다. 여서 '혹시'하는 마음으로 f-string으로 출력해보는데, (제출번호 71022654)

print(f"{bridge_num:.0f}")

맞았다.! 😮

 

int()와 f-string의 float rounding 방식이 다른 것일까?

Python f-string Doc 이긴 한데 봐도 궁극적으로 반올림하는 것인지, 내림하는 것인지 나오지 않아서 검색해보니 int()와 f-string 둘 다 rounding down 방식이라고 한다.

f-string

그럼 왜 결과가 달랐던 거지???

 

라는 의문이 스쳐갔지만, 원래 컴퓨터에서 float의 표현이 (1/2)+(1/4)+...와 같은 방식으로 이루어지므로, 알 수 없는 오차가 오답과 정답을 가른 것이 아닌가 생각하였다.

 

사실 이 문제에서 더 중요한 사실은 나누어 떨어지는 것이 분명한 정수 나눗셈에서는 // 연산자를 사용하자는 것이다. 나머지를 무시하기 때문에 의도한 결괏값을 얻을 확률이 훨씬 높아진다.

 

정수 나눗셈에서는 // 연산자를 사용하자.