풀이
뒤죽박죽 섞여있는 B로부터 A배열을 찾아내야한다. 이전 수에서 3으로 딱 나누어 떨어지거나, 이전 수에서 2를 곱한 수가 다음 수로 오게끔 순서대로 이루어진 배열을 찾으려면 어떻게 해야할까?
-
이 문제를 처음 읽어보고 하나의 트리 구조가 떠올랐다. 트리의 높이는 각 배열의 idx에 해당하는 layer이고, 그 안에 B에 주어진 값들이 들어갈 수 있는지 이를 count하는 트리다.
물론 전부 성립하지 않은 경우들만 존재하지만, 차례대로 맞는지 하나하나(브루트포스) 확인해보는 것이다. A라는 배열을 트리로 표현하여 다음 값으로 어떤 값이 올바를지 check하는 방법으로 진행하는 것이다.
위의 예시의 경우, 4부터 시작하는 경우, 8부터 시작하는 경우, 6,3까지 모두 도전했지만 실패한 케이스이다.
-
위의 트리 구조를 생각하며 다음 노드로 이동할때마다 조건을 만족하는지 검사해보자. 먼저, 이전에 A라고 생각했던 값에서 2를 곱한 값이거나, 아니면 이전 값에서 3을 나눈 값인지를 검사한다. 당연히 두 조건에 만족하지 않는다면?? A 배열이 될 수 없기 때문에 그 이후의 경우의 수들은 검사할 필요가없다. 즉, 자연스럽게 이 문제는 백트래킹이라는 것을 알 수 있다.
-
A배열에 순서대로 하나씩 넣으며 길이 N에 도달하게 되면, A 배열을 만족하는 구나! 하고 이를 정답 케이스로 분류할 수 있다. 하지만, 혹시 모를 예외가 있을 수 있으니, 각 노드에 대해 방문처리를 해주며, 마지막 N에 도달하였을 때 모든 노드에 방문을 했는지를 검사하는 것이 좋을 것 같다.
# 16936 나3곱2
n=int(input())
b=list(map(int,input().split()))
def backtrack(layer):
global answer
global visited
if layer==n-1:
not_answer=False
# 실제 n까지 도달했을 경우 혹시 모르니까, visited에 B배열의 값이 모두 있는지 확인하며 예외처리
for element in b:
if element not in visited:
not_answer=True
break
if not_answer:
return
# 위의 조건을 모두 통과한 경우 A 배열에 해당하기 때문에 바로 정답 호출한 후 system exit
print(*answer)
exit()
for idx in range(n):
if b[idx] in visited:
continue
else:
# 다음 노드가 이전 노드의 2배인지, 1/3배 인지 검사하기.
if answer[-1]*2==b[idx] or answer[-1]==b[idx]*3:
# 문제 없는 경우 탐색을 시작해보기. visited처리 및 answer에 넣어보기
visited.append(b[idx])
answer.append(b[idx])
backtrack(layer+1)
# 재귀함수로 탐색을 해봤는데 아닌걸로 판단되어 exit()까지 도달 못했으면
# 직전에 visited처리한 노드랑 answer에 넣어뒀던 노드 빼기!
visited.pop()
answer.pop()
for possible_case in b:
answer=[]
visited=[]
answer.append(possible_case)
visited.append(possible_case)
# 처음 주어진 B 배열의 요소 하나하나를 시작점으로 잡고 탐색 시작해보기
backtrack(0)
