henongj   3년 전

1010번 문제는 결국 조합문제였고 , 조합은 팩토리얼을 쓰고, 팩토리얼 문제는 늘 정수형 자료형의 범위를 훌쩍 넘더군요.

그래서 이 문제를 풀 때 다음과 같은 방법을 썼습니다.

8C3 이라고 한다면 8 7 6 을 multipleTable 에 , 3 2 1 을 divideTable에 넣고 그것들을 따로 곱해서

answer 와 temp에 저장헤서 answer / temp 를 답하는 방식입니다.

마찬가지로 9C6 이면 9 8 7 , 3 2 1 을 사용합니다.

답은 맞았습니다. 맞았는데

자료형을 넘는 계산이 나올 때마다 스트레스를 받습니다.

큰 수를 계산하는 방법을 떠올리면 문자열 방식으로 입력한 다음 자릿수 올림을 처리하는 로직인데

이 방법도 굉장히 큰 수의 곱셈끼리는 대응이 안 됩니다. 속도도 느리고.

대체 커다란 수는 어떻게 다뤄야 하나요. 

경우의 수 문제에 대응할 수 있는 명쾌한 방법이 있나요?

yijw0930   3년 전

곱하거나 나누는 수들 각각의 최대치 및 최종 결과가 int형 이내인 경우에 한해서 확장유클리드 알고리즘을 이용한 modular inverse를 구현하는 방식으로 해결할 수 있을 것 같습니다.

충분히 큰 소수인 M을 잡고 곱할때는 a*b%M, 나눌 때는 a*(모듈러 M에 대한 b의 역수)%M 을 사용하면 됩니다.

henongj   3년 전

덕분에 새로운 것을 알았습니다. 

연등시간 이외에도 공부할 거리가 생겼네요

정말 감사합니다 (_ _ )

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