백준 17252번, 17253번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	17252번 (삼삼한 수) : 실버 4 17253번 (삼삼한 수2) : 실버 3

17253번 문제. 17252번은 N이 최대 2147483647(2^31-1)이다.

---

풀이

 사실 삼삼한 수 2를 먼저 풀고나서 삼삼한 수 1을 검색해봤는데 N의 최댓값이 훨씬 적어서 삼삼한 수 2의 코드를 그대로 복붙해서 제출했다. 따라서 필자는 삼삼한 수 2를 기준으로 설명할 것이다.

 

 이 문제는 그리디하게 풀이할 수 있다. 풀이 순서는 다음과 같다.

• n에 가장 근접하면서 n이하의 3의 거듭제곱 3^k = a를 찾는다.
• (n - a) = n'와 k - 1을 인자로 재귀함수에 넘겨준다. 같은 3의 거듭제곱은 사용할 수 없기 때문에 k - 1을 넘긴다.
• 최종적으로 재귀함수에 넘어온 n'값이 0이 되면 삼삼한 수라는 뜻이다.

이 문제를 풀 때 간과한 사실은 n에 가장 근접하면서 n이하의 3의 거듭제곱 a를 찾았다면, 해당 함수에서는 더이상 지수를 줄여가며 찾을 필요가 없다. 만약 n - a를 했을 때 삼삼한 수가 아니었다면, n - a/3의 값에서 다시 재귀해야하는데, a/3 이하의 3의 거듭제곱으로는 n - a/3을 만들 수 없기 때문이다. 이를 간과하고 코드를 작성하다가, 직접 만든 극한 케이스인 6078832729528464401을 넣어봤더니 TLE가 나왔다. 해당 숫자는 초항이 1이고 공비가 3인 등비수열의 40번째 항까지 모두 더한 값에 1을 더한 값이다. 3으로 절대 나누어 떨어지지 않는 수이다. 3^40 > 2^63 > 3^39이기 때문에 이를 간과한다면 최대 39!번의 연산을 해야하니 당연히 TLE가 나게 된다. 삼삼한 수 1(17252)에서는 해당 부분을 신경쓰지 않아도 된다.

코드

#include <bits/stdc++.h>
using ll = int64_t;
using namespace std;

ll my_pow(ll a, int b) {
	if (b == 0) return 1;
	if (b == 1) return a;

	ll t = my_pow(a, b / 2);
	if (b % 2 == 1) return t * t * a;
	else return t * t;
}

bool sol(ll num, int exp) {
	if (num == 0) return true;
	if (num < 0) return false;
	ll val;
	for(; exp >= 0; exp--) {
		val = my_pow(3, exp);

		if (num < val) {
			continue;
		}
		return sol(num - val, exp - 1);
	}
	return false;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	ll n;

	cin >> n;
	cout << (n != 0 && sol(n, 39) ? "YES" : "NO");
}