[PS] 백준 #21968. 선린의 터를

문제 정보

• 난이도: 실버 IV
• 문제 주소: https://www.acmicpc.net/problem/21968
• 이 문제를 푼 이유: 그룹 연습 Div.2

 

문제

드높은 남산 위에 우뚝 선

(중략)

세워라 반석 위에

선린의 터를

1899년, 여러분들은 대한제국 고종 황제의 칙령을 받아 한국 최초의 실업교육기관인 관립상공학교를 세울 터를 선택해야 한다.

대한제국에서 학교를 지을만한 터는 여러 개 있는데, 각 터는 서로 다른 자연수를 번호로 갖고 있다. 특히, 선린의 터의 번호는 $3^k$꼴의 자연수가 최대 한 번씩 더해진 자연수이다(단, $k \ge 0$). 즉, 선린의 터의 번호는 $1(=3^0), 3(=3^1), 9(=3^2), 27(=3^3), 81(=3^4), 90(=3^2+3^4), 91(=3^0+3^2+3^4)$ 등이 있다.

여러분은 $N$번째로 작은 선린의 터를 탐색하라는 명령을 받았다. $N$번째 선린의 터를 구하는 프로그램을 작성하자.

 

나의 풀이

이 문제는 이진수, 삼진수를 변환하는 문제라서 알고리즘 자체는 간단했다. 먼저 입력값을 2진수로 변환하여 벡터에 저장하고, 그 벡터의 정보를 가지고 3진수 값을 만들어냈다. 근데 계속 123456789123을 입력했을 때 값이 이상하게 나왔다. 처음에는 int로 풀어서 안됐지만 long long 자료형으로 바꿔도 계속 다른 값이 나왔다. 한참을 고민해보다가 pow 함수를 일일이 tp 에 3을 거듭 곱하는 형식으로 바꾸니 코드가 통과했다. pow 함수는 double 타입을 리턴하는데 이 타입은 최대 $10^{15}$ 단위까지 나타낼 수 있다. 근데 우리가 출력하려는 값은 $10^{17}$ 단위이기 때문에 값에 오류가 생긴 것 같다.

#include <bits/stdc++.h>

using namespace std;

vector<int> vec;

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

	long long t, n; cin >> t;
	while (t--) {
		cin >> n;
		vec.clear();

		// 1. n을 이진수로 변환
		while (n > 0) {
			vec.push_back(n % 2);
			n = (long long) (n / 2.0);
		}

		// 2. 삼진수로 다시 변환
		long long l = 0;
		for (int i = 0; i < vec.size(); i++) {
			long long tp = 1;
			if (vec[i] == 1) {
				for (int j = 0; j < i; j++) tp *= 3;
				l += tp;
			}
		}
		cout << l << endl;
	}
}