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

14 Jun 2019

Reading time ~2 minutes

이번 문제는 저번의 삼삼한 수 에 이어

전북대 경진대회에 나왔던 문제로

백준(boj) 17253번 삼삼한 수 2 라는 문제입니다.

문제링크

풀이

저번에는 수의 제한이 작아서 3의 배수 합의

조합을 구하는 방식으로 풀이를 했었는데요,

이번에는 그렇게 하기에는 너무나 많은 경우의 수가 나오기에 그렇게 할 수가 없습니다.

이번에는 총 19자리 까지 가능하다고 하였는데, 이는 long long 형의 최대 길이입니다.

만약 long long 범위인 19자리 이상을 요구한다면

그건 매우.. 노가다성 문제로 문자열로 바꾸어 계산을 해주어야 하는 문제입니다.

무쪼록 여기는 다행히도 19자리 까지임으로 long long 형을 사용 해주시면 됩니다!

이번에는 역방향 탐색을 이용하게 되는데요,

미리 3의 제곱은 배열 혹은 벡터에 저장을 해주셔야 합니다.

저같은 경우에는

threes.push_back(1);
	for (int i = 0; i < 40; i++) {
		threes.push_back(threes[i] * 3);
	}

이 방식으로 3의 제곱들을 넣어 주었습니다~

왜 40까지냐? 하면 19자리 까지 나올 수 있는 최대 3의 제곱이 3의 39승이기 때문입니다.

마지막 하나는 여유를 주기 위해 넣어 주었습니다.

그럼 이렇게 만들어진 배열로 어떻게 계산을 해야 할까요?

while (maax>=0) {
				if( n >= threes[maax])
					n -= threes[maax];
				maax--;
				if (n == 0) {
					n = 1;
					result = 1;
					maax = 0;
					break;
				}
				else if (maax < 0) {
					maax = 0;
					result = -1;
					break;
				}
			}

이런식으로 해주면 됩니다.

maax 가 먼저 -1 이 되면 삼삼한 수가 아니고 (즉 n 이 0으로 안떨어지면)

n 이 먼저 0이 되면 삼삼한 수가 되는 겁니다.

빅오 는 생각 할 필요가 없을 정도로 작습니다.

n 에 따라서 영향이 있긴 하지만, 상수 정도로 작아지거든요.

굳이 따지자면 log3(n) 이라고 할 수 있겠네요.

코드

#include <iostream>
#include <vector>>

using namespace std;

vector<long long > threes;
int maax = 0;
long long  n;
int result = 0;

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

		while (maax <= 40 && n >= threes[maax])
			maax++;
		if (maax == 41)
			maax = 40;
		if (n == 0)
			result = 0;
		else if (n == threes[maax - 1])
			result = 1;
		else {
			maax--;
			while (maax>=0) {
				if( n >= threes[maax])
					n -= threes[maax];
				maax--;
				if (n == 0) {
					n = 1;
					result = 1;
					maax = 0;
					break;
				}
				else if (maax < 0) {
					maax = 0;
					result = -1;
					break;
				}
			}
		}
		if (result <= 0)
			cout << "NO";
		else
			cout << "YES";
	
	return 0;
}