[BOJ] 17253 - 삼삼한 수 2

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

BOJ - 삼삼한 수 2

문제 유형: 수학

문제 난이도: Silver III

시간 제한: 1초

메모리 제한: 256MB

 

문제

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

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

예를 들어, 10^9는 3^0+3^3+3^4로 나타낼 수 있으므로 삼삼한 수이다. 하지만 7과 18은 삼삼하지 않다.

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

 

입력

첫째 줄에 9,223,372,036,854,775,807보다 작거나 같은 음이 아닌 정수 N이 입력된다.

 

출력

입력된 수가 삼삼하다면 YES, 그렇지 않다면 NO를 출력한다.

 

풀이

0은 우선 불가능하다.

문제가 묻는 것은 결국, 삼진수로 표현 시 1또는 0으로만 표현되느냐를 묻는다.

즉, 그리디하게 3^39부터 뺄 수 있는경우 하나씩만 빼보면서 베이스를 낮춰본다.

이렇게 하여 N = 0이 된경우 YES를 출력한다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n;
    cin >> n;

    if (n == 0) {
        cout << "NO\n";
        return 0;
    }

    ll x = 1;
    for (int i = 0; i < 39; i++) {
        x *= 3;
    }

    for (int i = 0; i < 40; i++) {
        if (n >= x) n -= x;
        x /= 3;
    }

    if (n != 0) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }

    return 0;
}