BOJ - 삼삼한 수 (17252)

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

17252번: 삼삼한 수

 

 

이 문제는 풀 수 있는 방법이 크게 두 가지가 있습니다.

 

1. 수학적 풀이

2. 완전탐색

 

수학적 풀이는 다음에 소개하기로 하고, 이번에는 완전탐색으로 푸는 방법을 소개하겠습니다.

아무래도 코딩 테스트에서 완전탐색이 자주 나오기 때문이죠.

 

약 3^21 정도면 2,147,483,647 을 넘어서게 됩니다.

 

그러므로 3^0부터 3^21 까지 1번 또는 0번 사용해서 만들 수 있는가를 알아내기 위한 완전탐색을

수행하면 시간복잡도는 O(2^N) 으로 최대 2^21 = 약1000000 으로 시간안에 충분히 가능합니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
vector<ll> v;
ll k;
 
void sol(ll total, int cur) {
    if (total == 0) {    // total 이 0에 도달하게 되면 그러한 조합을 찾았으므로 종료합니다.
        cout << "YES";
        exit(0);
    }
    if (cur == v.size() || total < 0) return;    // cur 이 v의 끝에 도달하거나, total 값이 0 아래로 떨어지게 되면 더이상 희망이 없으므로 return 합니다.
    
    // 각 스텝에서 취할수 있는 액션은 두 가지 입니다.
    sol(total, cur + 1);    // 현재 스텝에서의 값을 사용하지 않는다.
    sol(total - v[cur], cur + 1);    // 현재 스텝에서의 값을 한 번 사용한다.
}
 
 
int main() {
    ll a = 2147483647;
    ll b = 1;
    while (a >= b) {
        v.push_back(b);
        b *= 3;
    }
 
    cin >> k;
    if(k != 0) sol(k, 0);    // 0인 경우는 제외시켜 줍니다.
    cout << "NO";
}