[BAEKJOON] 백준 17253: 삼삼한 수 2 (C#)

문제 링크

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

 

 

문제

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

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

예를 들어, 109는 30+33+34로 나타낼 수 있으므로 삼삼한 수이다. 하지만 7과 18은 삼삼하지 않다.

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

 

 

입력

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

 

 

출력

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

 

 

 

통과한 답안

namespace _17253
{
    internal class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());

            Console.WriteLine(isTrit(N) ? "YES" : "NO");
        }

        static bool isTrit(long n)
        {
            if (n == 0) return false;

            while (n > 0)
            {
                long remainder = n % 3;
                if (remainder > 1)
                {
                    return false;
                }
                n /= 3;
            }

            return true;
        }
    }
}

 

숫자 N이 주어졌을 때, N이 삼삼한 수인지 판단하는 문제이다.

삼삼한 수는 해당 숫자를 3의 거듭제곱을 겹치지 않고 한번씩만 더해서 만들 수 있는 수이다.

예를 들어 109는 3^0 + 3^3 + 3^4로 나타낼 수 있는 삼삼한 수이다.

 

삼삼한 수는 3의 거듭제곱을 0개 혹은 1개 사용해서 더했을 때 나타나는 수로

3진수로 표현할 수 있는 수인지 확인하면 판단할 수 있다.

 

따라서 N이 0인지 판단하여 0이라면 삼삼한 수가 아니고

(3의 거듭제곱이 최소 1개 이상 포함되어야 하므로)

3진수로 표현할 수 있는 수라면 삼삼한 수가 된다.