백준 11051 - 이항 계수2

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

11051번: 이항 계수 2

 

문제 요약)

팩토리얼 계산 결과를 10007로 나누었을 때의 나머지를 구하는 문제

 

key point) 부동소수점의 이해 필요

import math
N, K = map(int, input().split())

if (N-K)<K:
    K=N-K

num1 = math.factorial(N)
num2 = math.factorial(K)*math.factorial(N-K)

# num1과 num2는 반드시 나누어 떨어짐(팩토리얼의 연산 결과는 항상 정수)
# /와 //의 연산 결과가 다름
# / : 실수형 연산
# // : 정수형 연산
print(int(num1/num2))
print(num1//num2)

print(int(num1/num2)%10007)
print(num1//num2%10007)

위의 코드를 돌리면 아래와 같은 출력값이 나온다.

너무 숫자가 커서 잘 안보이는데

int(num1/num2)

==> 270288240945436551019305908463402626133344424635003137400602091930237777421360473851797325724922730460543802875678603168471867361078540080081808473288115110060581000433119131429793939577717447508918397345219433071259594386723113371250852722071254367796680880783950950640887679135140232038177361100800

num1//num2

==>

270288240945436569515614693625975275496152008446548287007392875106625428705522193898612483924502370165362606085021546104802209750050679917549894219699518475423665484263751733356162464079737887344364574161119497604571044985756287880514600994219426752366915856603136862602484428109296905863799821216320

이러한 결과가 나온다.

 

17번째 자릿수에서부터 다른 숫자가 나오는데 결과값이 2500자리이므로 매우매우매우 큰 오차가 발생하는 것을 알 수 있다.

 

Q. 소수점도 아니고 둘다 정수인데 왜 오차가 생길까?

컴퓨터의 연산은 10진수 체계가 아닌 2진수 체계이다. 파이썬은 연산을 할 때 10진수로 입력한 값을 2진수로 바꾸어 연산을 하는데, 입력된 숫자가 매우 커질 경우 문제가 발생한다.

1000!의 결과값은 무려 2500자리가 나오기 때문에 일의 자리까지 정확한 값을 얻을 수 없다.

이렇게 매우 큰 수를 부동소수점으로 표현하게 될 경우, 엄청 큰 수를 오차없이 콘솔창에 표기하는 것은 불가능하다.

(컴퓨터 체계가 이렇게 생겨먹음;)

 즉 요약하자면, 매우 큰 수는 부동소수점로 표현할 때 정확하게 표현이 불가능해 큰 수의 연산에서 오차가 발생한다.

 

Q. 그렇다면 /가 아닌 //를 쓰는 이유는 무엇일까?

정의를 잘 살펴보자.

/는 나누기를 하는 실수형 연산자이고, //는 몫을 구하는 정수형 연산자이다.

어차피 팩토리얼의 결과값은 정수형이기 때문에 /나 //를 써도 결과값을 정수로 변환하면 동일한 결과가 나온다.

단, 매우 큰 숫자는 부동소수점의 표현으로 인하여 서로 다른 값이 나온다.

//는 실수형이 아닌 정수형 연산자이므로 BIGINTEGER가 적용되어 숫자를 정확하게 끝까지 받아들여 정확한 연산을 할 수 있기 때문에 /가 아닌 //를 사용해야된다.

 

 

느낀 점)

이 문제는 복잡한 문제가 아닌 단순 구현형 문제이다.

하지만, 컴퓨터 체계의 연산을 모르고 /를 사용한다면 전혀 다른 결과값이 나오게 된다.

매우 큰 숫자를 정수형 결과가 나오도록 나눌 때는 반드시 정수형 연산자인 //를 사용하자!

 

+) factorial은 따로 구현이 가능하지만 그냥 math모듈의 factorial 클래스를 임포트하여 편리하게 사용할 것!