C++로 n에 가장 가까우면서 m으로 나누어 떨어지는 수 찾기

두 개의 정수 n과 m이 주어졌을 때, n에 가장 가까우면서 m으로 나누어 떨어지는 수를 찾는 문제를 생각해 볼 수 있습니다. 만약 조건을 만족하는 수가 여러 개라면 절댓값이 가장 큰 수를 선택해야 하며, n이 m으로 완전히 나누어 떨어지는 경우에는 n 자체를 그대로 반환하면 됩니다.

예를 들어 n = 13, m = 4라고 한다면, 4의 배수 중 13에 가장 가까운 수는 12이므로 출력 결과는 12가 됩니다.

해결 알고리즘

이 문제는 다음 단계를 통해 간단하게 해결할 수 있습니다.

• 몫 q := n / m 을 구하고, n1 := m × q 로 첫 번째 후보 값을 계산합니다.
• n × m > 0 이면(즉, n과 m의 부호가 같으면) n2 := m × (q + 1) 로, 그렇지 않으면 n2 := m × (q − 1) 로 두 번째 후보 값을 계산합니다.
• |n − n1| < |n − n2| 이면 n1을 반환하고, 그렇지 않으면 n2를 반환합니다.

여기서 n과 m의 부호 관계를 확인하는 이유는, 정수 나눗셈이 0을 향해 잘림(truncation) 처리되기 때문에 부호에 따라 더 가까운 배수의 방향이 달라지기 때문입니다.

예제 코드

#include<iostream>
#include<cmath>
using namespace std;

int findClosest(int n, int m) {
    int q = n / m;
    int n1 = m * q;
    int n2 = (n * m) > 0 ? (m * (q + 1)) : (m * (q - 1));
    if (abs(n - n1) < abs(n - n2))
        return n1;
    return n2;
}

int main() {
    int n = 13, m = 4;
    cout << "Closest for n = " << n << ", and m = " << m << ": " << findClosest(n, m) << endl;

    n = 0; m = 8;
    cout << "Closest for n = " << n << ", and m = " << m << ": " << findClosest(n, m) << endl;

    n = 18; m = -7;
    cout << "Closest for n = " << n << ", and m = " << m << ": " << findClosest(n, m) << endl;
}

실행 결과

Closest for n = 13, and m = 4: 12
Closest for n = 0, and m = 8: 0
Closest for n = 18, and m = -7: 21

결과 분석

첫 번째 경우인 n = 13, m = 4에서는 12와 16 중 12가 13에 더 가깝기 때문에 12가 반환됩니다. 두 번째 경우인 n = 0, m = 8에서는 0이 이미 8로 나누어 떨어지므로 그대로 0이 반환됩니다. 세 번째 경우처럼 m이 음수일 때도 알고리즘이 올바르게 동작하여, -14와 -21 중 18과의 거리를 비교한 결과 21이 최종적으로 선택됩니다.

이 알고리즘은 나눗셈과 곱셈 몇 번만으로 답을 구하므로 시간 복잡도는 O(1)로 매우 효율적입니다.