C++에서 주어진 정수가 3의 거듭제곱인지 판별하는 방법

이 문제에서는 하나의 정수 N이 주어졌을 때, 주어진 정수가 3의 거듭제곱인지 아닌지를 판별하는 것이 우리의 과제입니다.

문제 이해를 위한 예시

입력 : N = 729
출력 : Yes

설명 −

36 = 729

729는 3을 여섯 번 곱한 값, 즉 3의 거듭제곱이므로 결과는 'Yes'입니다.

해결 접근 방식

이 문제는 3의 거듭제곱 값의 성질을 활용하면 매우 간단하게 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 32비트 int 자료형으로 표현할 수 있는 가장 큰 3의 거듭제곱은 3¹⁹ = 1,162,261,467입니다. 어떤 수 N이 3의 거듭제곱이라면, 그보다 큰 3의 거듭제곱인 3¹⁹는 반드시 N으로 나누어떨어집니다.

따라서 주어진 수 N이 양수이면서, 1162261467을 N으로 나눈 나머지가 0인지만 확인하면 됩니다. 나머지가 0이면 N은 3의 거듭제곱이고, 그렇지 않으면 3의 거듭제곱이 아닙니다.

예제 코드

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;

bool isPowerOf3(int n){
    if (n <= 0)
        return false;
    return 1162261467 % n == 0;
}

int main(){
    int n = 27;
    if (isPowerOf3(n))
        cout<<"The number is a power of 3";
    else
        cout<<"The number is not a power of 3";
    return 0;
}

출력 결과

The number is a power of 3

위 코드에서 n = 27은 3³에 해당하므로 3의 거듭제곱이 맞습니다. 따라서 isPowerOf3 함수가 true를 반환하고, 해당 메시지가 출력됩니다.

이 방법은 반복문이나 재귀 호출 없이 단 한 번의 나머지 연산만으로 답을 구할 수 있어 시간 복잡도가 O(1)로 매우 효율적이라는 장점이 있습니다.