728x90 반응형 중국인의 나머지 정리1 [algorithm] 백준 - 카잉 달력 이 문제는 시간 제한이 1초인 것에 유의해야하는 문제이다. 두 자연수의 최소 공배수까지 반복문을 돌며 나머지 값과 동일한 경우를 구하게 되면 40000 * 40000 이상의 연산은 1초를 넘게 되서 시간 초과가 난다. 참고로 최소 공배수까지 반복문을 도는 이유는, 최소 공배수를 기점으로 나머지가 0이 되기 때문에 x: y 또한 m: n이 될 것이므로, 그 이상의 수를 반복시킬 이유는 없어진다. 예를 들어 m:n = 10 : 12 일 경우, 최소 공배수는 60으로 x : y k번째 해 10:12 60 1 : 1 61 10: 12 120 1: 1 121 60을 주기로 계속 반복되는 것을 관찰 할 수 있다. 그렇다면 어떻게 시간 제한을 1초 내로 줄일 수 있을까? 반복문은 굳이 최소 공배수까지 돌 필요가 없다.. 2020. 11. 10. 이전 1 다음 728x90 반응형
