[BOJ/백준][Gold5] 16936 : 나3곱2 (C++)

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

16936번: 나3곱2

 

 

[난이도] Gold5
[유형] 수학

[풀이]
수열의 숫자들간의 관계를 그래프로 표현한 뒤, 모든 수에서 DFS를 돌려보면서
깊이가 N-1까지 도달했을 때, 즉 모든 수를 나누기3, 곱하기2 연산으로 방문을 완료했을 경우의 방문 순서를 출력해주면 됩니다.

예를 들어,
4 8 6 3 12 9
수열이 있을 경우
8을 만들려면 4 또는 24가 있어야 하는데 24는 수열에 없으므로
4->8 간선만 만들어주면 됩니다.
이런식으로 모든 수에 대해 어떤 수로부터 만들 수 있는지를 파악하여 간선을 만들어주면 됩니다.
숫자와 index를 매핑해주기 위해 map을 이용하였습니다.

 

#include <cstdio>
#include <vector>
#include <string>
#include <map>
using namespace std;
using ll = long long;
int N;
ll B[101];
map<ll,int> m;
vector<int> adj[101];
bool sol(int n,string s,int dep){
    if(dep==N-1){
        printf("%s",s.c_str());
        return true;
    }
    for(auto nxt : adj[n]) if(sol(nxt,s+" "+to_string(B[nxt]),dep+1)) return true;
    return false;
}
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%lld",&B[i]);
        m[B[i]]=i;
    }
    for(int i=0;i<N;i++){
        if(m.find(B[i]*3) != m.end()) adj[m[B[i]*3]].push_back(i);   
        if(B[i]%2==0 && m.find(B[i]/2) != m.end()) adj[m[B[i]/2]].push_back(i);
    }
    for(int i=0;i<N;i++) if(sol(i,to_string(B[i]),0)) return 0;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/16936.cpp