백준 1740 거듭제곱

www.acmicpc.net/problem/1740

1740번: 거듭제곱

이 문제는 solved.ac기준 브론즈 1로 매겨져 있지만, 얼핏 보면 상당히 어려울 수도 있다. 아니 솔직히 아직도 이게 왜 브론즈 1인지 조금 의문이다. 필자도 처음에는 이걸 어떻게 풀지?라는 어려움이 있었다. 알고 보면 간단하고 코드도 짧다. 하지만 모르면 어렵다.

 

핵심은 비트로의 표현이다!

위의 그림에서 보듯이 문제에서 N이 주어졌을 때, 그 N을 이진수로 표현하면 1001001 등으로 표현된다. 여기서 1이 바로 합에 사용된 숫자인 것이다. 아래 그림에서 이진수 101은 어떻게 10이 되는지를 살펴보자. 아래를 보면 101은 9와 1의 합이라는 것을 알 수 있고, 이진수101은 십진법으로 10이므로 곧 10번째로 작은 수다. N을 이진수로 바꿔주고, 켜진 비트로부터 3의 제곱수 중 어떤 것인지를 비트의 위치로부터 파악하는 것이다.

 

1은 켜진 비트, 0은 꺼진 비트이며 N이라는 숫자가 그 자체로 N번째로 작은 숫자임을 의미하게 되고, 그 N을 이진수로 변경했을 때 어떤 수들이 합에 관여하는지를 바로 알 수 있게 되는 것이다. 오른쪽에서부터 0번째면 3의 0승 = 1이 되고, 1번째면 3의 1승 = 3이 되는 식이다.

문제에서 주어지는 5천억이라는 어마어마하게 큰 숫자도 비트로 보게되면 1<<39 (bit shift연산) 보다 작은 수다. 즉 39개의 비트만 일일이 읽어보면 바로 답을 구할 수 있게 되는 것이다.

 

<주요 내용>

비트 연산, 이진법, 큰 수, long long, 거듭 제곱, 분할 정복

 

<코드>

C++ 코드와 파이썬 코드 총 3가지 버전이 있다. 

 

아래의 코드는 n/=2를 통해 주어진 n을 계속 줄여나가면서 이진법으로 표현된 수의 각 자릿수를 확인한다. 

이진법으로 변환할 때 십진법의 수를 2로 나눠나가며, 2로 나눈 나머지가 0,1로 표현되는 원리에 착안한 것이다.

b배열에 2진법 변환 후의 0,1등이 차곡차곡 쌓인다. 그리고 이후에 3을 거듭하여 곱하면서 지수를 키우고 N번째 작은 수를 구할 수 있다.

#include <iostream>
#define endl '\n'
typedef unsigned long long ull;
ull n;
int b[60];
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    int i = 0;
    ull ans = 0, temp = 1;
    while (n > 1)
    {
        b[i++] = n % 2;
        n /= 2;
    }
    b[i++] = 1;
    int j = 0;
    for (; j < i; j++)
    {
        temp = 1;
        for (int k = 0; k < j; ++k)
        {
            temp *= 3;
        }
        ans += temp * b[j];
    }
    cout << ans << endl;
    return 0;
}

 

아래의 버전은 재귀 함수와 분할 정복을 활용하여 거듭제곱을 구한 버전이다.

비록 거듭제곱의 횟수가 그리 많지 않아 큰 의미는 없지만, 연습 삼아 구현해보았다.

#include <iostream>
#define endl '\n'
using namespace std;
typedef long long ll;
ll n, ans;
ll power(int i)
{
    if (!i)return 1;
    ll temp = power(i / 2);
    if (i % 2)return temp * temp * 3;
    return temp * temp;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0; i < 40; ++i)if (n & (1LL << i))ans += power(i);
    cout << ans << endl;
    return 0;
}

 

아래는 파이썬 코드이다. bin( )함수를 통해 바로 이진법으로 변환하였으며, 앞에 나오는 '0b'를 떼어내기 위해 [2: ]만 취하였다.

import sys
si = sys.stdin.readline


def main():
    n = int(si())
    st = bin(n)[2:]
    exp, ans = len(st)-1, 0
    for e in st:
        if int(e):
            ans += 3**exp
        exp -= 1
    print(ans)


if __name__ == '__main__':
    main()