[BOJ-16936] 나3곱2

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

16936번: 나3곱2

---

[풀이]

나는 DFS를 이용하여 풀었다.

DFS+ 재귀함수 를 활용해야한다.

 

그리고 문제입력에서 수열B는 수열A의 순서를 임의로 섞은 것이기때문에

B의 원소를 차례대로 DFS탐색해야한다.

 

B의 원소 x라 할때

먼저, x의 값이 B에 속하는지 확인한다.

그리고 x가 3의배수라면, x의 나3값인 x//3이 B에 속한다면 x//3을 추가한뒤에 DFS탐색한다.

그리고 3의배수 여부 상관없이, x의 곱2값인 x*2가 B에속한다면 x*2를 추가한뒤에 DFS탐색한다.

 

문제를 꼼꼼히 읽어보고

재귀를 활용한 백트래킹과 DFS를 할 줄 안다면 풀 수있다.

---

import sys
input=sys.stdin.readline
#입력#
N=int(input())
B=[*map(int, input().strip().split())]

def dfs(x, cnt, A):
    #연산횟수가  N-1회라면
    if cnt==N-1:
        return A
    
    #x가 B에 있는가?
    if x in B:
        #x가 3에 나눠떨어지는 수인가?->나3연산
        if x%3==0:
            #x//3값이 B에 있다면
            if (x//3) in B:
                return dfs(x//3, cnt+1, A+[x//3])
        # x*2값이 B에 있다면
        if (x*2) in B:
            return dfs(x*2, cnt+1, A+[x*2]) #곱2연산

for i in range(N):
    x=dfs(B[i], 0, [B[i]])
    if not (x is None):
        print(' '.join(map(str,x)))
        break