문제

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번째로 작은 수를 출력한다.

예제 입력

4

예제 출력

9

내가 했던 풀이 방법

1. 입력받은 숫자를 BigInt로 변환해준다. (입력받은 숫자가 500,000,000,000 이하이기 때문에 범위를 초과할 수 있음)
2. 입력받은 숫자를 2진수로 변환해준다.
3. 2진수로 변환된 값을 3진수 변환 방법을 이용하여 10진수로 변환해준다. (문제에 "서로 다른 3의 제곱수의 합"이기 때문에 해당 방법이 가능하다.)
4. 10진수로 변환된 값을 String으로 변환한 뒤 출력해준다. (BigInt이기 때문에 그대로 출력하면 숫자 뒤에 n까지 포함되어 출력된다. 이를 제거해주기 위해 String으로 변환해준다.)

코드

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim();

let n = BigInt(input);
let binary = '';
while (true) {
  if (n === 0n) break;
  binary = (n % 2n) + binary;
  n = n / 2n;
}

let answer = 0n;
let pow = 0n;
for (let i = binary.length - 1; i >= 0; i--) {
  answer += BigInt(binary.charAt(i)) * getPow(pow++);
}

console.log(answer.toString());

function getPow(n) {
  let pow = 1n;
  for (let i = 0n; i < n; i++) {
    pow *= 3n;
  }
  return pow;
}

회고

3진수로 변환하는 코드를 작성했는데 "서로 다른"에 대한 조건을 해결할 수 없어서 다른 사람들의 풀이를 참고하게 된 문제.. 결과적으로 2진수 변환을 먼저 해주어야 했다는 점... 참신한 풀이이긴 하나 다음에 유사한 문제를 발견하면 그 때 기억할 수 있을 것인가... 조금이라도 기억을 오래하기 위해 기록하긴 하지만, 비트마스킹 문제는 정말 어렵고 어렵고 어려운 것 같다. 또, 숫자가 커지면서 거듭제곱 함수를 사용하면 값에 차이가 발생할 수 있다고 해서 거듭제곱을 함수로 구현했다. 문제를 풀기위해서는 가끔씩 편리한 메소드를 직접 구현해야 할 때가 있겠구나를 생각하게 됐다.