BOJ 2436 - 공약수
작년 12월 말, jungol 사이트에 있는 문제를 풀면서 당황한 적이 있다.
KOI 기출문제인 공약수를 풀어보려고 시도했는데 시간 초과에 걸려서 몇 시간을 고생했고, 아는 동생의 도움을 받아 겨우 풀 수 있었다.
사실 그동안 이 문제를 잊고 살다가.. 오랜만에 봤더니 훨씬 효율적으로 풀 수 있을 것 같아서 재도전했고 무난하게 성공!
그래서 내가 어떻게 풀었는지 개인적으로 정리해보려고 한다.
접근 방법
위키백과에 나와있는 최소공배수에 대한 설명을 살펴보자.
(적어도 하나가 0이 아닌) 두 정수의 최소공배수는 그 두 정수의 곱 나누기 최대공약수이다.
이 문제에서, 이 성질을 이용하면 정답으로 나와야 될 두 수가 최소공배수 * 최대공약수의 약수 중 하나라는 것을 알 수 있다.
그럼 모든 약수를 다 탐색해봐야하는가? 라고 생각할 수 있겠지만~ i가 약수라면 n/i도 약수이기 때문에 실제로는 sqrt(최소공배수 * 최대공약수) 까지만 살펴보면 된다.
그리고 반드시 두 수의 약수에는 최대공약수가 포함되어 있어야 하므로, 다음과 같이 생각해볼 수 있다.
long MUL = gcd * lcm
for(int i = gcd; i * i <= MUL; i += gcd)
if(i와 MUL/i의 최대공약수가 gcd와 같고 최소공배수가 lcm과 같은 경우)
첫 번째 자연수 = i
두 번째 자연수 = MUL/i
if(현재까지 찾은 첫 번째 자연수 + 두 번째 자연수의 최적값보다 지금 구한 값이 작은 경우)
최적값 갱신
이렇게 구현한 결과, Java 기준 68ms로 통과했다. 기존에 짰던 코드는 280ms였다…
BOJ에는 테스트 케이스가 6 180 하나 밖에 없는데 다른 사이트에는 케이스가 하나 더 공개되어 있으니 참고하면 좋다.
입력 : 2 86486400
출력 : 11648 14850