[BOJ] 17253 : 삼삼한 수 2

17253 : 삼삼한 수 2

문제

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

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

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

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

입력

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

출력

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

풀이

문제를 수학적으로 해석하자면, 음이 아닌 정수 n 을 3 의 제곱수 합으로 나타내는 데, 앞에 곱해진 값이 0 또는 1만 존재하는 수를 찾는 것이다.

109 = 3^0 + 3^3 + 3^4 이므로 YES
7 = 3^0 + 2 3^1 이므로 NO
18 = 2 3^2 이므로 NO

while 문을 통해 n 을 3 으로 나눠가며 나머지가 0 과 1 이 아닌 경우, 삼삼한 수가 아니라고 볼 수 있다.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	long long n;
	cin >> n;

	bool isSamSam = true;

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

	while (n)
	{
		int remainder = n % 3;
		if (remainder > 1)
		{
			isSamSam = false;
			break;
		}
		n /= 3;
	}

	if (isSamSam)
		cout << "YES";
	else
		cout << "NO";

	return 0;

}