두 개의 정수 P와 Q가 주어졌을 때, 다음 두 조건을 동시에 만족하는 가장 작은 정수 K를 구하는 문제입니다.
K % P = 0→ K는 P의 배수Q % K = 0→ K는 Q의 약수
만약 이러한 K가 존재하지 않으면 -1을 출력해야 합니다. 예를 들어 P = 2, Q = 8이라면 K = 2가 됩니다. 2 % 2 = 0이고, 8 % 2 = 0이기 때문입니다.
접근 방법
핵심 아이디어는 매우 간단합니다. 조건을 만족하는 K가 존재하려면 Q가 반드시 P로 나누어 떨어져야 합니다.
K는 P의 배수이면서 동시에 Q의 약수여야 합니다. 만약 P의 어떤 배수가 Q를 나눌 수 있다면, 그보다 작은 값인 P 자신도 당연히 Q를 나눌 수 있습니다. 따라서 판단 기준은 다음과 같습니다.
Q % P == 0이면 답은 P입니다. P의 배수 중 가장 작은 값이 P 자신이고, 이때 이미 두 조건을 모두 만족하기 때문입니다.- 그렇지 않다면 조건을 만족하는 K가 존재하지 않으므로 -1을 반환합니다.
C++ 구현 예제
코드
#include <iostream>
using namespace std;
int getMinK(int p, int q) {
// Q가 P로 나누어 떨어지면 K = P가 최솟값
if (q % p == 0)
return p;
// 나누어 떨어지지 않으면 조건을 만족하는 K가 없음
return -1;
}
int main() {
int p = 24, q = 48;
cout << "K의 최솟값은: " << getMinK(p, q);
return 0;
}출력 결과
K의 최솟값은: 24
동작 원리
P = 24, Q = 48인 경우를 살펴보겠습니다. 48 % 24 == 0이므로 함수는 24를 반환합니다. 실제로 24 % 24 = 0이고 48 % 24 = 0이므로 두 조건을 모두 만족하며, P의 배수 중 가장 작은 값은 P 자체이기 때문에 이것이 곧 최솟값입니다.
시간 복잡도
단 한 번의 나머지 연산으로 해의 존재 여부를 판별할 수 있으므로, 시간 복잡도는 O(1)입니다. 입력 크기와 무관하게 항상 일정한 시간에 결과를 얻을 수 있는 매우 효율적인 풀이입니다.