[백준 16936번] [Bruteforce] 나3곱2

Approach

잘 생각해보면 3과 2는 서로소이므로, 배타적으로만 존재가능하다.

 

예를 들어 v[i]라는 숫자가 존재한다고 했을 때, v[i] / 3이 존재하거나 v[i] * 2만 존재해야 한다.

왜냐하면, 3과 2는 서로소이기 때문에 3으로 나눈 것을 아무리 2를 곱해도 절대로 3으로 나눈 것을 커버할 수 없다.

 

추가적으로 수열의 크기가 N이기 때문에, v[0]으로 나올 수 있는 후보를 하나씩 체크해서 가능한 경우를 모두 확인해주면 된다.

이때, 주어진 수에 v[i] / 3이나 v[i] * 2가 존재하는지를 쉽게 파악하기 위해서 set 자료구조를 활용하였다.

시간 복잡도는 $O(n^2logn)$이므로 시간 안에 충분히 통과한다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};


int main() {
    fastio;
    int n;
    cin >> n;

    vector<ll> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }

    for(int i = 0; i < n; i++){
        vector<ll> result = {v[i]};
        set<ll> s(v.begin(), v.end());
        for(ll cur = v[i]; result.size() < n; result.push_back(cur)){
            s.erase(cur);
            if(s.count(cur * 2)) cur *= 2;
            else if(cur % 3 == 0 && s.count(cur / 3)) cur /= 3;
            else break; // Not found
        }
        if(result.size() == n){
            for(auto &p : result){
                cout << p << " ";
            }
            cout << "\n";
            return 0;
        }
    }   
}