삼삼한 수

삼삼한 수

문제 설명

준하는 3의 거듭제곱인 수만 사용하여 만들 수 있는 수를 보면 삼삼한 느낌을 받는다.

이 느낌을 정확히 설명하자면, 3의 거듭제곱인 수들을 겹치지 않고 한번씩만 더해서 어떤 수 x를 만들 수 있다면 그 수는 삼삼하다고 한다. 삼삼한 수는 3의 거듭제곱인 수가 반드시 하나 이상 포함되어야 한다.

예를 들어, 109는 3

0

+3

3

+3

4

로 나타낼 수 있으므로 삼삼한 수이다. 하지만 7과 18은 삼삼하지 않다.

준하는 삼삼한 수가 얼마나 더 있는 지 알아보려고 한다.

예제 입력

109

예제 출력

YES

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(process.platform === "linux" ? "dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let n = Number(input[0]);
  // 0 이 입력으로 들어오면 리턴
  if (n === 0) {
    console.log("NO");
    return;
  }
  while (0 < n) {
    /**
     * n 에서 3을 나눈 값이 2 일 때가 의미하는 것은
     * 3진수의 관점에서 봤을 때 2가 나오면 해당 자리의 수를
     * 2번 썼다는 의미이기 때문에 규칙에 위배됨 따라서 2가 나오면
     * NO 출력 후 return
     * 예를 들어서 n 이 18일 때
     * case 1 : n / 3 = 6 n % 3 = 0
     * case 2 : n / 3 = 2 n % 3 = 0
     * case 3 : n / 3 = 0.66... n % 3 = 2
     * 이런 식으로 나오게 되는데 이를 3진수로 표현하면 200 이 된다 
     * 이 200의 의미는 3 ** 2 를 2번 썼다는 의미 이므로 9 + 9 
     * 해당 문제의 규칙에 위배 되게 된다.
     */
    if (n % 3 === 2) {
      console.log("NO");
      return;
    }
    n = Math.floor(n / 3);
  }
  console.log("YES");
};

solution(input);

아이디어 / 접근법

1. n이 0 이라면 바로 출력
2. n 을 계속 나눠주며 나머지가 2라면 NO 출력
3. 아니라면 계속 나눠줌

후기

처음에는 그냥 n에서 가장 가까운 3의 제곱수를 찾은 다음 그 수에서 3씩 나눠가면서 구해주다가 마지막에 1, 3, 9 가 나오면 YES 아니면 NO 를 출력해주도록 했음 근데 시간초과가 나게 되었음. 그래서 생각을 해보다가 해당 숫자를 3진수의 관점에서 보면 2가 나머지로 나올 때 해당 자리의 숫자를 2번 썼다는 걸 파악하게 되었고 그렇게 풀다보니 성공했음