C++로 구하기: C의 배수이면서 [A, B] 범위에 속하지 않는 최소 양의 정수

문제 개요

세 개의 정수 A, B, C가 주어졌을 때, 다음 두 조건을 동시에 만족하는 가장 작은 정수 X를 구하는 것이 목표입니다.

• X는 C로 나누어떨어져야 합니다. 즉, X mod C = 0을 만족해야 합니다.
• X는 닫힌 구간 [A, B]에 포함되지 않아야 합니다.

예를 들어 A = 5, B = 10, C = 4라고 가정해 보겠습니다. 이때 정답은 X = 4입니다. 4는 4로 나누어떨어지면서 동시에 [5, 10] 범위에 속하지 않기 때문입니다.

해결 아이디어

이 문제는 간단한 논리만으로 O(1) 시간 안에 해결할 수 있습니다.

1. C가 [A, B] 범위에 없는 경우: C 자체가 이미 두 조건을 모두 만족하는 최솟값이므로, 그대로 C를 반환합니다.
2. C가 [A, B] 범위에 있는 경우: B보다 큰 C의 첫 번째 배수를 계산하여 반환합니다.

B보다 큰 첫 번째 배수는 다음 공식으로 손쉽게 구할 수 있습니다.

((B / C) * C) + C

여기서 (B / C) * C는 B 이하에서 C의 최대 배수를 의미하고, 여기에 C를 한 번 더하면 B를 초과하는 바로 다음 배수가 됩니다.

예제 코드

#include <iostream>
using namespace std;
int findMinNumber(int a, int b, int c) {
    if (c < a || c > b)
        return 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] 범위 안에 포함되어 있으므로, 두 번째 규칙이 적용됩니다. (B / C) * C = (4 / 2) * 2 = 4이고, 여기에 C인 2를 더하면 6이 됩니다. 따라서 조건을 만족하는 최솟값은 6입니다.

복잡도 분석

• 시간 복잡도: O(1) — 단순 산술 연산만 수행합니다.
• 공간 복잡도: O(1) — 추가적인 메모리가 필요하지 않습니다.