백준: 16936 나3곱2

문제

16936번: 나3곱2

 

문제 풀이

 정수 하나를 사용하여 연산을 N-1번 적용한다. 적용할 수 있는 연산은 정수가 3으로 나누어 떨어지는 경우 3으로 나누거나, 2를 곱하는 경우가 있다. 문제에 제시된 조건에 따라 DFS를 통하여 구하면 쉽게 문제를 풀 수 있다. DFS로 푸는 것은 다른 문제에서도 많이 다루었고 `서로소`의 성질을 이용하여 3으로 가장 많이 나누어 떨어지는 수부터 정렬하는 방식을 사용하여 푸는 방법이 있다.

 

만약, DFS로 풀고자 한다면 DFS의 deapth가 N - 1이 될때까지 반복하고 3으로 나누어 떨어지는 경우와, 2를 곱하는 경우에 따라 탐색하고자 하는 경우의 수를 추가하면 된다.

 

코드

from sys import stdin


if __name__ == '__main__':
    n = int(stdin.readline())
    b = list(map(int, stdin.readline().split()))
    b = {num: 0 for num in b}

    for num in b.keys():
        cur_num = num

        while True:
            if num % 3 == 0:
                b[cur_num] += 1
                num //= 3
            else:
                break

    sort_dict = sorted(b.items(), key=lambda x: (-x[1], x[0]))
    print(*[key for key, _ in sort_dict])