[BOJ] 백준 17252 삼삼한 수 코드 C++

12 Jun 2019

Reading time ~1 minute

이 문제는 전북대학교 프로그래밍 경진 대회에 나왔던 문제로

백준 17252 번 문제 삼삼한 수 라는 문제입니다.

문제링크

풀이

간단하게 완전 탐색으로 푸시면 됩니다.

우선적으로 21억.xxxx 를 넘지 않는,

즉 인트 범위를 벗어나지 않는 수가 주어 져야 하는데,

이는 3^ 19 승이 저 수를 벗어나지 않는 최대의 수입니다.

이를 이용해 배열을 만들면

20칸의 배열 혹은 벡터에 들어가게 되곘지요.

이것을 차례대로 모두 더하는 완전 탐색을 해주면 됩니다.

단! 주의해야 할 점은,

0은 삼삼한 수가 아닙니다.

0은 보는 관점에 따라서 삼삼한 수가 될수도, 안될 수도 있는데

현재 문제에는 따로 언급이 없고, 0은 삼삼한 수가 아닌 것으로 되어있습니다.

그점만 주의 해주시면 큰 문제 없을 거 같습니다.

코드

#include <iostream>
#include <vector>>

using namespace std;

vector<unsigned int> threes;
int maax = 0;
int n;
int result = 0;
void check(unsigned int mount, unsigned int nt) {
	if (nt == maax+1  ) {
		if ( n == mount)
			result = 1;
	}
	else {
		check(mount + threes[nt], nt + 1);
		check(mount, nt + 1);
	}
}

int main() {
	threes.push_back(1);
	for (int i = 0; i < 19; i++) {
		threes.push_back(threes[i] * 3);
	}
	cin >> n;

	while ( maax <= 19 && n >= threes[maax])
		maax++;
	if (maax == 20)
		maax = 19;
	if (n == threes[maax])
		result = 1;
	else {
		check(0, 0);
	}
	if (n == 0)
		result = 0;
	if (result == 0)
		cout << "NO";
	else
		cout << "YES";
	cin >> n;
	return 0;
}