C++에서 a의 b제곱(a^b)에 가장 가까운 x의 배수 찾기

세 개의 정수 a, b, x가 주어졌을 때, a^b 값에 가장 가까운 x의 배수를 구하는 문제입니다.

예를 들어 a = 5, b = 4, x = 3이라면 결과는 624입니다. 5⁴ = 625인데, 625에 가장 가까운 3의 배수가 624이기 때문입니다.

해결 접근 방법

이 문제는 간단한 수학적 접근으로 해결할 수 있습니다. 다음 단계를 순서대로 따르면 됩니다.

먼저 목표값을 계산합니다: num := a^b
num을 x로 나눈 값의 내림(버림)을 구합니다: f := floor(num / x)
왼쪽(작은 쪽) 후보와 오른쪽(큰 쪽) 후보를 각각 계산합니다:
- 왼쪽 후보: cl = x * f
- 오른쪽 후보: cr = x * (f + 1)
마지막으로 두 거리를 비교하여 더 가까운 값을 반환합니다: min(num – cl, cr – num)

이 방법이 작동하는 이유는 어떤 양의 정수든 x로 나누었을 때 몫의 배수 사이에 위치하기 때문입니다. 즉, cl ≤ num < cr이 항상 성립하므로, 이 두 후보 중 하나가 반드시 가장 가까운 배수가 됩니다.

C++ 구현 예제

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

long long getClosest(int a, int b, int x) {
    long long num = pow(a, b);
    int f = floor(num / x);
    long long cl = x * f;
    long long cr = x * (f + 1);
    if ((num - cl) < (cr - num))
        return cl;
    else
        return cr;
}

int main() {
    int a = 5, b = 4, x = 3;
    cout << "Find closest element: " << getClosest(a, b, x);
}

실행 결과

Find closest element: 624

참고 사항

a^b의 값은 매우 빠르게 커질 수 있으므로, 오버플로우를 방지하기 위해 결과를 저장할 때 long long 타입을 사용하는 것이 좋습니다. 또한 입력 범위가 크다면 pow 함수 대신 직접 반복문으로 거듭제곱을 계산하거나, 부동소수점 연산 오차를 피하기 위해 정수 기반 거듭제곱 함수를 사용하는 것이 안전합니다.