백준 16936 나3곱2 python3

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

16936번: 나3곱2

주어진 입력이 처음에 어떤 수열인지 판단하는 문제입니다.

규칙은 간단합니다.

x 부터 시작해 x가 3의 배수이면 3으로 나눌 수 있고, x가 어떤 수든 2를 곱할 수 있습니다.

 

3을 나누고 2를 곱하는 규칙 밖에 없으므로 배열에서 중복된 값이 나올 수는 없습니다. 

왜냐하면 x 를 기준으로 y가 되었는데 x = y 라고 한다면 (x / 3^n) * 2^m = y 인 것이고, 이는 2^m / 3^n = 1을 만족하는 m, n 이 존재하는 것입니다. 하지만 2와 3은 서로소이므로 m, n은 0 밖에 없습니다.

즉 중복이 되는 경우는 없습니다.

 

그러므로 주어진 배열의 수를 순서대로 2를 곱하고 3으로 나눌 수 있으면 나누고를 dfs와 유사하게 진행하여 최종적으로 전체 배열의 원소를 다 탐색하게 된다면 정답이 됩니다.

 

이 때 index 별로 탐색 여부를 확인하거나 해도 되지만, 중복이 없으므로 단순히 카운트로 탐색 여부를 확인하여도 됩니다.

 

코드는 다음과 같습니다.

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

# 3으로 나누거나 2를 곱하므로 중복 불가
def calc(num, cnt, arr, result):
    num2 = num * 2
    num3 = num // 3
    r = num % 3
    
    if cnt == len(arr):
        return result
    
    if num2 in arr:
        result.append(num2)
        return calc(num2, cnt + 1, arr, result)
    
    elif r == 0 and num3 in arr:
        result.append(num3)
        return calc(num3, cnt + 1, arr, result)
    
    else:
        result = []
        cnt = 0
        return result
        
def print_list(List):
    for i in range(len(List)):
        print(List[i], end = ' ')

for num in arr:
    result = [num]
    result = calc(num, 1, arr, result)
    
    if len(result) == len(arr):
        print_list(result)
        break