문제링크
1740번: 거듭제곱
3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를
www.acmicpc.net
문제
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번째로 작은 수를 출력한다.
풀이
서로 다른 3의 제곱수를 사용하기 때문에 2진수 처럼 3의 제곱수를 나열할 수 있다.
... 81 27 9 3 1
0 0 0 0 1 = 1
0 0 0 1 0 = 3
0 0 0 1 1 = 4
0 0 1 0 0 = 9
0 0 1 0 1 = 10
...
2진수로 표현된 수는 N번째로 작은 3의 제곱수의 합이 된다. 따라서 입력 받은 수를 2진수로 바꿔주고 2진수 계산처럼 3의 제곱수를 더해나가면 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <iostream>
#include <queue>
using namespace std;
unsigned long long n;
queue<int> q;
int main() {
cin >> n;
// 2진수로 변환
while (n) {
q.push(n % 2);
n = n / 2;
}
unsigned long long res = 0;
unsigned long long tmp = 1;
// 계산
while (q.empty() == false) {
res = res + q.front() * tmp;
tmp = tmp * 3;
q.pop();
}
cout << res;
}
|
cs |
메모
풀이 방법이 도저히 떠오르지 않아서 고민을 많이 했다. 어떻게 정답률이 50프로가 넘는 것이지.. 세상에는 정말 똑똑한 사람들이 많은 것 같다..ㅎㅎ
