Boj 16936 c++ 나3곱2

나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다.

• 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 한다.
• 곱2: x에 2를 곱한다.

나3곱2 게임을 진행하면서, 만든 수를 모두 기록하면 수열 A를 만들 수 있다. 예를 들어, x = 9, N = 6이고, 적용한 연산이 곱2, 곱2, 나3, 곱2, 나3인 경우에 A = [9, 18, 36, 12, 24, 8] 이다.

수열 A의 순서를 섞은 수열 B가 주어졌을 때, 수열 A를 구해보자.

수열 B의 각각의 원소에 대하여 DFS를 돌려주었다. 만약 시작점이 해가 아니면 출력되지 않고, 해를 찾는 순간 출력되고 끝난다.

#include<iostream>
#include<vector>
typedef long long ll;
using namespace std;
vector<ll> B;
vector<ll> A;
int N;
bool is_B(ll U){
    for(int i=0; i<N; i++){
        if(U==B[i])
            return true;
    } return false;
}

void DFS(ll U, int cnt){
    if(cnt==N){
        for(int i=0; i<N; i++){
            cout<<A[i]<<" ";
        } return;
    }
    if(is_B(U*2)){
            A.push_back(U*2);
            DFS(U*2, cnt+1);
            A.pop_back();}
    if(is_B(U/3) && U%3==0){
            A.push_back(U/3);
            DFS(U/3, cnt+1);
            A.pop_back();
            } return;
}

int main(){
    cin>>N;
    ll tmp;
    for(int i=0; i<N; i++){
        cin>>tmp;
        B.push_back(tmp);
    }
    for(int i=0; i<N; i++){
        A.push_back(B[i]);
        DFS(B[i], 1);
        A.pop_back();
    }
}