[코테] 백준 브루트 포스 16936번 문제

16936번 : 나3곱2

문제 링크

https://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에 포함된 원소는 10^18 보다 작거나 같은 자연수이다.

출력

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

문제풀이

수열을 순서대로 넣었을 때 N과 같을때 출력하면 된다. 다만 중요한건 나3 연산을 할 때 x는 3으로 나누어 떨어져야 한다는 점만 주의하면 된다.

N = int(input())
arr = list(map(int, input().split()))

temp = []
def back() :
    if len(temp) == N :
        print(*temp)
        return

    for i in range(N) :
        if not temp : 
            temp.append(arr[i])
            back()
            temp.pop()
        
        elif arr[i] not in temp : 
            if divmod(temp[-1], 3) == (arr[i], 0) :
                temp.append(arr[i])
                back()
                temp.pop()
            elif temp[-1] * 2 == arr[i] :
                temp.append(arr[i])
                back()
                temp.pop()
back()