[ BOJ ] 16936 : 나3곱2 ( GOLD 5 ) / Python

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

16936번: 나3곱2

문제

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

풀이 과정

1. A 에 2를 곱했을 때 B가 되는 쌍을 찾아 묶었다.

A가 이전에 이미 다른 수에서 2를 곱했을 때의 B 였을 수도 있으므로, 배열을 먼저 정렬하고, 해시 값을 통해 연속으로 2를 곱했을 때 여러 수가 묶일 수 있도록 구현했다.

dic = {}
for i in range(1, n):
    for j in range(i):
        if arr[j] * 2 == arr[i]:
            if dic.get(arr[j], -1) == -1:
                dic[arr[i]] = [arr[j], arr[i]]
                vis[i] = 1
                vis[j] = 1
            else:
                go = dic[arr[j]]
                del dic[arr[j]]
                go.append(arr[i])
                dic[arr[i]] = go
                vis[i] = 1

{8: [4, 8], 12: [3, 6, 12]}

 

2. 한 그룹의 끝 수 를 3으로 나누었을 때 다른 그룹의 시작 수 가 되는 그룹 쌍을 찾아 연결했다.

방문 처리를 하지 않은 남은 숫자는 한 개의 수를 가진 그룹으로 묶어 모든 그룹을 노드로 만들었고, 어떤 그룹의 끝 수를 3으로 나누었을 때 다른 그룹의 시작 수가 되어 연결되는 관계가 있다면 엣지로 기록했다. (링크드 리스트로 만듬)

node = []
for i in range(n):
    if vis[i] == 0:
        node.append([arr[i]])
for v in dic.values():
    node.append(v)

edge = [-1 for _ in range(len(node))]

for i in range(len(node)):
    for j in range(len(node)):
        if i == j: continue

        if node[i][-1] % 3 == 0 and node[i][-1] // 3 == node[j][0]:
            edge[i] = j

Node :  [[9], [4, 8], [3, 6, 12]]
Edge :  [2, -1, 1]

 

3. 링크드 리스트의 루트 노드를 찾고, 루트 노드부터 차례대로 링크드 리스트를 탐색하며 노드의 수들을 차례대로 출력한다.

root = -1
for i in range(len(node)):
    if edge.count(i) == 0:
        root = i
        break

while root != -1:
    for a in node[root]:
        print(a, end=' ')
    root = edge[root]

 

 

항상 정답이 존재하는 경우에만 입력으로 주어져서 가능한 풀이라고 생각한다.

전체 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))
arr.sort()

# 1. 이중 반복문으로 2배 쌍 찾기
vis = [0 for _ in range(n)]

dic = {}
for i in range(1, n):
    for j in range(i):
        if arr[j] * 2 == arr[i]:
            if dic.get(arr[j], -1) == -1:
                dic[arr[i]] = [arr[j], arr[i]]
                vis[i] = 1
                vis[j] = 1
            else:
                go = dic[arr[j]]
                del dic[arr[j]]
                go.append(arr[i])
                dic[arr[i]] = go
                vis[i] = 1

# 2. 남은 걸로 나누기 3 쌍 찾기
node = []
for i in range(n):
    if vis[i] == 0:
        node.append([arr[i]])
for v in dic.values():
    node.append(v)

edge = [-1 for _ in range(len(node))]

for i in range(len(node)):
    for j in range(len(node)):
        if i == j: continue

        if node[i][-1] % 3 == 0 and node[i][-1] // 3 == node[j][0]:
            edge[i] = j

# 3. 루트 찾기
root = -1
for i in range(len(node)):
    if edge.count(i) == 0:
        root = i
        break

while root != -1:
    for a in node[root]:
        print(a, end=' ')
    root = edge[root]