개발 블로그

문제 링크 : www.acmicpc.net/problem/16936

문제

나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를 구해보자.

입력

첫째 줄에 수열의 크기 N(2 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 수열 B가 주어진다. B에 포함된 원소는 1018 보다 작거나 같은 자연수이다.

출력

나3곱2 게임의 결과 수열 A를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

접근 방법

주의할 점 : B에 포함된 원소는 10^18 보다 작거나 같은 자연수이므로 자료형을 long long 으로 해줘야 한다. int 형으로 하면 출력초과나 틀렸습니다가 나온다. 

주어진 조건대로 직관적으로 풀어보았다.

1. 주어진 수열 B의 첫번째 요소를 x로 설정한다.

1-1. x곱2 연산을 한 결과가 (수열 B에 있고 x로 설정한 적이 없으면) 수열 A에 push 하고 DFS를 호출한다. 

1-2. x곱2 연산을 한 결과가 (수열 B에 없거나 x로 설정한 적이 있으면) 나3 연산을 진행한다.

     1-2-1) x가 3의 배수이고, x/3이 수열 A에 있고 ,x/3을 x로 설정한 적이 없으면 수열 A에 x/3을 push 하고 DFS를 호출한다. 

이 과정을 반복해서 수열 A의 크기가 N이 되면 DFS를 빠져나갈 때 바로 빠져나가기 위해 iscontinue를 false로 설정한 뒤 수열 A의 원소를 출력한다. 

예로 A = {4 8 6 3 12 9} 이고 x=4로 설정한 후 실행했다고 해보자.

4*2 = 8 -> 8은 수열 A에 존재하고 x=4이므로 visited한 적 없으므로 수열A에 8을 push하고 DFS를 호출한다. 

8*2 = 16은 수열 A에 존재하지 않으므로 16을 수열 A에서 pop 하고 DFS를 빠져나간다.

다시 8에 대해 나3 연산을 수행해본다. 8은 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

다시 4에 대해 나3연산을 수행해본다. 4도 3의 배수가 아니므로 수열 A에서 8을 pop하고 DFS를 빠져나간다. 

이제 x=8로 설정하고 위와 같이 반복한다.

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int visited[100] = {0};
int N;

pair<bool, int> isIn(long long num){					
    for(int i = 0; i<N; i++){
        if(vecB[i]==num) return make_pair(true, i);		//<해당 숫자가 있는지,수열 B에서 몇번째 인덱스인지>
    }
    return make_pair(false, -1);
}

bool iscontinue = true;
void DFS(long long x, int cnt){
    
    if(cnt==N){
        iscontinue = false;
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        printf("\n");
        return;
    }
    
    //곱2
    pair<bool, int> p = isIn(2*x);
    if(p.first==true && visited[p.second]==0){
        visited[p.second] = 1;
        vecA.push_back(x*2);
        DFS(x*2, cnt+1);
        if(iscontinue){
            vecA.pop_back();
            visited[p.second] = 0;
        }else return;
       
    }

    
    //나3
    if(x%3 == 0){
        pair<bool, int> p2 = isIn(x/3);
        if(p2.first==false) return;
        else if(p2.first==true && visited[p2.second]==0){
            visited[p2.second] = 1;
            vecA.push_back(x/3);
            DFS(x/3, cnt+1);
            if(iscontinue){
                vecA.pop_back();
                visited[p2.second] = 0;
            }else return;
           
        }
    }
    
    if(iscontinue==false) return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){			//주어진 수열 B에서 하나씩 x로 지정해서 DFS 돌림
        visited[i] = 1;
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        if(iscontinue==true){					//수열 A 찾지 못했을 경우 pop 하고 다음 요소를 x로 지정해서 반복
            vecA.pop_back();
            visited[i] = 0;
        }else break;
    }
    
    return 0;
}

아래의 방법은 velog.io/@hschoi1104/BOJ-16936-%EB%82%983%EA%B3%B12

를 참고해서 위의 코드를 수정한 것이다. 

//
//  BF_BOJ16936_나3곱2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/03.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

vector<long long> vecB;
vector<long long> vecA;
int N;


void DFS(long long x, int cnt){

    if(cnt==N){
        for(int i = 0; i<N; i++){
            cout << vecA[i] << " ";
        }
        exit(0);
    }
    

    if(x%3==0 && find(vecB.begin(), vecB.end(), x/3)!=vecB.end()){
        vecA.push_back(x/3);
        DFS(x/3, cnt+1);
        vecA.pop_back();
    }
    if(find(vecB.begin(), vecB.end(), 2*x)!=vecB.end()){
        vecA.push_back(2*x);
        DFS(2*x, cnt+1);
        vecA.pop_back();
    }
    return;
}


int main(){

    cin>>N;
   
    long long num;
    for(int i = 0; i<N; i++){
        scanf("%lld", &num);
        vecB.push_back(num);
    }
    
    for(int i = 0; i<vecB.size(); i++){
       
        vecA.push_back(vecB[i]);
        DFS(vecB[i], 1);
        vecA.pop_back();
            
    }
    
    return 0;
}