취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 21966번 문제인 (중략)이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/21968 

각 선린의 터의 번호에 대하여 모든 3^k꼴의 정수는 선린의 터의 번호를 구성하는데에 사용되거나 사용되지 않는다. 이 때 3^k가 선린의 터의 번호를 구성하는 데에 사용되었다면 1을, 아니라면 0을 k오름차순으로 적으면 이진수와 바로 대응시킬 수 있는 선린의 터의 삼진수 표현을 얻을 수 있다. 특히, N번째 선린의 터의 번호의 삼진수표현을 이진수로 해석하면 N이 나온다는 점을 관찰하자.

위 이진수와 선린의 터의 번호의 삼진수 표현의 대응관계를 이용하여 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <deque>
using namespace std;
typedef long long ll;

void solve() {
	ll N; cin >> N;
	ll ans = 0;
	deque<ll> dq;
	while (N > 0) {
		ans *= 3;
		if (N & 1) dq.push_back(1);
		else dq.push_back(0);
		N >>= 1;
	}
	ll exp3 = 1;
	while (!dq.empty()) {
		ans += dq.front() * exp3;
		dq.pop_front();
		exp3 *= 3;
	}
	cout << ans << '\n';
}

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

	int T; cin >> T;
	while (T--) solve();
}