문제 개요
이번 글에서는 흥미로운 알고리즘 문제를 하나 살펴보겠습니다. 세 개의 정수 A, B, C가 주어졌을 때, 다음 두 조건을 동시에 만족하는 가장 작은 양의 정수 X를 구하는 것이 목표입니다.
X mod C = 0, 즉 X는 C로 나누어 떨어져야 합니다.
X는 닫힌 구간 [A, B]에 포함되지 않아야 합니다.
예를 들어 A = 5, B = 10, C = 4라고 가정해 보겠습니다. 이때 X의 값은 4가 됩니다. 4는 4로 나누어 떨어지고(4 mod 4 = 0), 구간 [5, 10]의 범위 밖에 있기 때문입니다.
해결 접근 방법
이 문제는 간단한 관찰만으로 상수 시간 안에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
경우 1: C 자체가 구간 [A, B]에 속하지 않는다면, C가 곧 정답입니다. C는 당연히 C로 나누어 떨어지고(C mod C = 0), 구간 밖에 있으므로 두 조건을 모두 만족합니다.
경우 2: C가 구간 [A, B] 안에 있다면, B보다 큰 C의 첫 번째 배수를 구해 반환합니다. 그 배수는 C로 나누어 떨어지면서 구간 [A, B]보다 크므로 역시 조건을 만족합니다.
B보다 큰 C의 첫 번째 배수는 ((B / C) * C) + C 공식으로 계산할 수 있습니다. 여기서 B / C는 정수 나눗셈이므로 (B / C) * C는 B 이하에서 C의 가장 큰 배수가 되고, 여기에 C를 한 번 더 더하면 B보다 큰 다음 배수를 얻게 됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int findMinNumber(int a, int b, int c) {
// C가 구간 [a, b]에 없으면 C가 곧 정답
if (c < a || c > b)
return c;
// b보다 큰 c의 첫 번째 배수 계산
int res = ((b / c) * c) + c;
return res;
}
int main() {
int a = 2, b = 4, c = 2;
cout << "Minimum number X: " << findMinNumber(a, b, c);
}
실행 결과
Minimum number X: 6
동작 과정 분석
위 예제에서 a = 2, b = 4, c = 2입니다. 먼저 c = 2가 구간 [2, 4] 안에 있는지 확인합니다. 2 ≤ 2 ≤ 4이므로 구간 안에 존재합니다. 따라서 두 번째 단계로 넘어가 b보다 큰 c의 첫 번째 배수를 계산합니다. (4 / 2) * 2 + 2 = 4 + 2 = 6이 되어 결과값 6이 출력됩니다.
시간 복잡도
이 알고리즘은 비교 연산과 산술 연산을 몇 번만 수행하면 답을 구할 수 있으므로 시간 복잡도는 O(1)입니다. 입력 크기와 무관하게 항상 일정한 시간에 실행된다는 점이 이 풀이의 가장 큰 장점입니다.