문제 개요
두 양의 정수 n과 k가 주어졌을 때, 다음 조건을 만족하는 양의 정수 x를 찾는 것이 목표입니다.
(x % k) × (x / k) == n
예를 들어 n = 4, k = 6이라고 가정해 보겠습니다. 이때 정답은 10입니다. 실제로 계산해 보면 (10 % 6) × (10 / 6) = 4 × 1 = 4로, 주어진 조건을 정확히 만족하며 그보다 작은 x로는 조건을 충족할 수 없습니다.
접근 방법
이 문제의 핵심은 나머지 연산의 성질을 활용하는 것입니다. 어떤 수 x를 k로 나눈 나머지를 r이라 하면, x는 다음과 같이 표현할 수 있습니다.
x = (x / k) × k + r
여기서 조건식 (x % k) × (x / k) = n에 대입하면, 몫(x / k)은 n / r이 됩니다. 따라서 x는 다음 공식으로 구할 수 있습니다.
x = (n / r) × k + r
단, r이 0이면 곱셈 결과도 0이 되어 양수 n을 만들 수 없으므로, 나머지 후보 r은 1부터 k − 1 사이의 값만 고려합니다. 이 범위에서 n의 약수에 해당하는 r을 모두 검사하고, 그중 x가 가장 작아지는 값을 선택하면 됩니다.
구현 예제
#include <iostream>
#include <climits>
using namespace std;
// 두 값 중 작은 값을 반환하는 헬퍼 함수
int minValue(int x, int y) {
return (x > y) ? y : x;
}
// 조건을 만족하는 최소 x를 구하는 함수
int getX(int n, int k) {
int x = INT_MAX;
// 나머지 후보를 k-1부터 1까지 역순으로 검사
for (int rem = k - 1; rem > 0; rem--) {
// 나머지가 n의 약수인 경우만 유효
if (n % rem == 0)
x = minValue(x, rem + (n / rem) * k);
}
return x;
}
int main() {
int n = 4, k = 6;
cout << "x의 최솟값: " << getX(n, k);
}
실행 결과
x의 최솟값: 10
동작 과정 살펴보기
n = 4, k = 6일 때 코드가 어떻게 동작하는지 단계별로 확인해 보겠습니다.
- r = 5: 4 % 5 ≠ 0이므로 제외
- r = 4: 4의 약수 → x = 4 + (4 / 4) × 6 = 10
- r = 3: 4 % 3 ≠ 0이므로 제외
- r = 2: 4의 약수 → x = 2 + (4 / 2) × 6 = 14
- r = 1: 4의 약수 → x = 1 + (4 / 1) × 6 = 25
후보 값 중 가장 작은 10이 최종 답이 됩니다.
시간 복잡도
가능한 나머지 범위가 1부터 k − 1까지이므로, 시간 복잡도는 O(k)입니다. k가 크지 않은 입력에서는 충분히 효율적으로 동작합니다. 참고로 INT_MAX를 사용할 때는 <climits> 헤더를 함께 포함하는 것이 안전합니다.