[BOJ]백준 17252/17253번: 삼삼한 수, 삼삼한 수2

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

17252번: 삼삼한 수

3의 거듭제곱인 수들을 중복해서 사용하지 않고 더해서 삼삼한 수 X가 될 수 있는지 구하는 문제

 

중복이 허용되지 않는 조건때문에 단순한 재귀함수로 구현가능했다

 

예제1에서, X가 109일 경우 109보다 작은 81까지 배열에 저장해준다

index	0	1	2	3	4	5
n[index]	1	3	9	27	81	243
include	O	X	X	O	O	-

재귀 호출을 트리로 표현했을 때

① 일단 X보다 작은 3의 거듭제곱 수들을 순서대로 배열에 저장하고

② 재귀함수를 호출, 내림차순으로 배열을 돌면서 그 숫자를 더할지or안더할지를 호출해준다

③ 모든 경우의 수에서 한 번이라도 x가 완성되면 true 반환

#include <cstdio>
int x, n[21], i=1, t = 1;
bool func(int dep, int num) {
	if (!dep)return num==x;
	return func(dep - 1, num + n[dep]) || func(dep - 1, num);
}
int main() {
	scanf("%d", &x);
	for (; i < 21&&t <= x; i++, t *= 3)n[i] = t;
	printf("%s", func(i-1, 0)&&x ? "YES" : "NO");
	return 0;
}

 

+하지만 아주 간단한 풀이가 있었다

그것은 바로 숫자를 3진수로 변환해서 각 자리 숫자가 0,1 인지만 확인하면 되는것 ^-T

ex. 109(10) -> 1101(3), 298 -> 10201(3)

 

삼삼한수(17252) 풀이:

#include <cstdio>
int main() {
	int x;
	scanf("%d", &x);
	if(!x) { printf("NO"); return 0; }
	while (x) {
		if (x % 3 > 1) { printf("NO"); return 0; }
		x /= 3;
	}
	printf("YES");
	return 0;
}

삼삼한수2(17253) 풀이: 

#include <cstdio>
int main() {
	long long x;
	scanf("%lld", &x);
	if(!x) { printf("NO"); return 0; }
	while (x) {
		if (x % 3 > 1) { printf("NO"); return 0; }
		x /= 3;
	}
	printf("YES");
	return 0;
}