[백준] 16936번 나3곱2 - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제

---

---

---

💡 문제

나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를 출력한다. 항상 정답이 존재하는 경우에만 입력으로 주어지며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

---

💭 접근

이 문제를 보았을 때 출력의 경우 "정답이 여러가지인 경우에는 아무거나 출력한다." 라고 하지만 사실 이 문제는 우선 항상 정답이 존재하는 경우만 입력으로 주어지며, 2와 3은 서로소이기 때문에 정답은 유일할 수 밖에 없다.

따라서 가능한 경우 1가지만 고려하면 된다.

위 사실을 알았다면 간단한 DFS를 활용하여 입력으로 주어진 수열에서 어떤 숫자가 첫번째 숫자가 될지 모르기에, 첫번째 숫자를 바꿔가면서 가능한 한가지 정답을 도출해내면 된다.

---

📒 코드

import sys

def dfs(start, depth):
    if depth == n:
        print(*ans)
        sys.exit()

    if start % 3 == 0 and start // 3 in num:
        ans.append(start // 3)
        dfs(start // 3, depth + 1)
    
    if start * 2 in num:
        ans.append(start * 2)
        dfs(start * 2, depth + 1)

n = int(input())
num = list(map(int, input().split()))

for i in range(n):
    ans = [num[i]]
    dfs(num[i], 1)

---

💭 후기

문제의 제목에서부터 힌트를 얻을 수 있는 문제.

---

🔗 문제 출처

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

---