코딩 일기장/CodingTest
[백준]이항 계수3/11041 풀이 JAVA
minWachya
2021. 7. 4. 20:07
반응형
문제
자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N)
출력
(NK)를 1,000,000,007로 나눈 나머지를 출력한다.
풀이(JAVA)
모듈러 연산과 페르마 소정리를 이용해서 푸는 문제였다.
ㅡㅡ이렇게 완전 깊고깊은 수학 공식을 알아야하는 문제 개싫음 그냥 식을 제공해줬으면 함
처음에는 메모이제이션으로 풀었다가 숫자가 너무 커서 시간초과 걸림...
메모이제이션이 내가 젤 잘하는 건데......................
모듈러랑 무슨...페르마 소정리!??!! 참내....
근데 이렇게 푸니까 시간도 빠르게 걸리고 용량도 덜 차지함ㄷ
...다양한 풀이법을 알고 있어야 겠다.
반응형