이 글에서는 어떤 수를 다른 수의 거듭제곱들로 표현할 수 있는지 판별하는 문제를 다룹니다. 두 개의 수 x와 y가 주어졌을 때, x의 각 거듭제곱을 최대 한 번씩만 사용하여 y를 표현할 수 있는지 확인해야 합니다.
입력: x = 4, y = 11
출력: true
설명: 4^2 − 4^1 − 4^0 = 11 이므로 y는 x의 거듭제곱으로 표현할 수 있습니다.
입력: x = 2, y = 19
출력: true
설명: 2^4 + 2^1 + 2^0 = 19 이므로 y는 x의 거듭제곱으로 표현할 수 있습니다.
입력: x = 3, y = 14
출력: false
설명: 14는 3^2 + 3^1 + 3^0 + 3^0 형태로만 나타낼 수 있지만, 같은 거듭제곱 항을 두 번 사용할 수 없기 때문에 표현이 불가능합니다.
풀이 접근 방법
19를 2의 거듭제곱으로 표현한 예시를 분석해 보면 다음과 같은 일반화된 식을 세울 수 있습니다.
c0(x^0) + c1(x^1) + c2(x^2) + c3(x^3) + … = y …(1)
여기서 계수 c0, c1, c2는 각각 −1, 0, +1 중 하나의 값만 가질 수 있습니다. −1은 해당 항을 빼는 경우, +1은 더하는 경우, 0은 해당 항을 포함하지 않는 경우를 의미합니다.
c1(x^1) + c2(x^2) + c3(x^3) + … = y − c0
x로 묶어 정리하면,
c1(x^0) + c2(x^1) + c3(x^2) + … = (y − c0) / x …(2)
식 (1)과 (2)를 비교하면 원래 문제와 같은 구조의 작은 문제가 반복된다는 것을 알 수 있습니다. 즉, 해가 존재하려면 (y − ci)가 x로 나누어 떨어져야 하며, ci는 −1, 0, +1 중 하나여야 합니다.
따라서 y가 0보다 큰 동안 [(y−1) % x == 0] 또는 [y % x == 0] 또는 [(y+1) % x == 0] 중 하나를 만족하는지 검사하고, 어느 조건도 만족하지 않는다면 해가 존재하지 않는다고 판단하면 됩니다.
C++ 구현 예시
#include <bits/stdc++.h>
using namespace std;
int main(){
int x = 2, y = 19;
// y>0인 동안 나누어 떨어지는지 검사
while (y>0) {
// y-1이 x로 나누어 떨어지는 경우
if ((y - 1) % x == 0)
y = (y - 1) / x;
// y가 x로 나누어 떨어지는 경우
else if (y % x == 0)
y = y / x;
// y+1이 x로 나누어 떨어지는 경우
else if ((y + 1) % x == 0)
y = (y + 1) / x;
// 어떤 조건도 만족하지 않으면
// y는 x의 거듭제곱으로 표현 불가능
else
break;
}
if(y==0)
cout<<"y는 x의 거듭제곱으로 표현할 수 있습니다.";
else
cout<<"y는 x의 거듭제곱으로 표현할 수 없습니다.";
return 0;
}
실행 결과
y는 x의 거듭제곱으로 표현할 수 있습니다.
결론
이 튜토리얼에서는 하나의 수를 다른 수의 거듭제곱들로 표현할 수 있는지 확인하는 방법을 살펴보았습니다. 현재 값 y와 그 앞뒤 값인 (y−1), (y+1)이 x로 나누어 떨어지는지 차례로 검사하면서 값을 반복적으로 줄여 나가는 간단하고 효율적인 접근 방식으로 문제를 해결했습니다.
또한 이 문제에 대한 C++ 프로그램을 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.