[백준] 1740번 : 거듭제곱 (C++)

1740번 : 거듭제곱

---

문제)

3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다.

이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를 들어 30은 27과 3의 합이므로, 이러한 수에 포함된다.

한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 N번째로 작은 수를 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 N이 주어진다. N은 500,000,000,000 이하의 자연수이다.

 

 

 

출력 :

첫째 줄에 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 N번째로 작은 수를 출력한다.

 

 

 

 

 

 

풀이)

#include <iostream>
#include <bitset>
#include <string>
 
using namespace std;
 
int main()
{
    // 수가 매우 커질 수 있으므로 long long을 사용한다.
    long long n;
    cin >> n;
 
    string temp = bitset<64>(n).to_string();
    
    long long result = 0;
    long long seq = 1;
    for (int i = temp.length() - 1; i > -1; i--)
    {
        if (temp[i] == '1')
        {
            result += seq;
        }
        seq *= 3;
    }
 
    cout << result;
 
    return 0;
}
 

 

 

---

출처 : https://www.acmicpc.net/problem/1740 

1740번: 거듭제곱