[BF] 16936번 나3곱2

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

알고리즘

• Brute Force
• Back Tracking

풀이

포인트

• 가능한 모든 경우의 수를 탐색하되, 나3곱2의 조건이 충족되는 경우만 살펴본다 (백트래킹)

Back Tracking

문제에서는 순서가 뒤죽박죽으로 된 수열 B가 주어진다. 우선 여기 있는 애들을 기반으로 수열 A가 만들어지므로, B에 있는 숫자들을 defaultdict 자료 구조를 가지는 exist에 기록한다. 이는 추후에 나3곱2에 해당하는 숫자가 있는지 탐색하는 시간을 줄여주기 위함이다.
이후에는 평소처럼 재귀를 이용해 Brtue Force을 해준다. 다만, 나3곱2에 해당하는 조건만 탐색하므로, 정확하게는 백트래킹이라 함이 맞을 것이다. 백트래킹 조건은 for문 안에 if조건에서 걸러주었다.

이렇게 백트래킹으로 구현하며 걱정되었던 점은, n이 최대 100이고 각 자리수마다 나3곱2 조건을 살펴보므로 시간 복잡도가 $O(2^{100})$이라 생각했다. 그러면 당연히 시간초과가 뜨는데, 백트래킹으로 조건 제한을 추가하여, 최악의 시간 복잡도는 피한 것(?)이 아닌가하는 생각이 들었다.

[Source Code]

from collections import defaultdict
n = int(input())
b = list(map(int,input().split()))
exist = defaultdict(bool)
for i in b:
    exist[i] = True
a = [0]*n
def go(index,n,before):
    if index == n:
        print(' '.join(map(str,a)))
        exit()
        return
    for i in range(n):
        if before == 0:
            a[index] = b[i]
            go(index+1,n,b[i])
        else:
            if (before % 3 == 0 and exist[before // 3] and before // 3 == b[i]) or (exist[before * 2] and before * 2 == b[i]):
                a[index] = b[i]
                go(index+1,n,b[i])
go(0,n,0)