백준_12852_1로 만들기 2

문제

12852번: 1로 만들기 2

풀이

N이 10이라고 할때, 경우의 수를 트리의 형태로 나열 할 수 있다. 같은 수가 다른 자리에서 여러번 등장할 수 있으므로 트리의 레벨 개념을 도입하였다. (N*level의 2차원 배열을 두었다고 생각할 수 있다.)

문제에서 N은 10^6보다 작은 자연수이므로, 메모리의 한계를 고려하여 defaultdict와 dict를 이용하여 아래의 코드처럼 표현하였다.

코드

from collections import defaultdict
N = int(input())
tree = defaultdict(dict) # child: {lv:p}
nums = [N]
lv = 0

# 1이 나올 때까지 트리 작성
while 1 not in nums :
    lv = lv + 1
    temp = list()
    for n in nums :
        if n%2==0 :
            m = int(n/2)
            tree[m][lv] = n
            temp.append(m)
        if n%3==0 :
            m = int(n/3)
            tree[m][lv] = n
            temp.append(m)
        if n>1 :
            m = n-1
            tree[m][lv] = n
            temp.append(m)
    nums = temp

# 경로 찾기
num = 1
ans = [str(num)]
print(lv)
while num!=N :
    num = tree[num][lv]
    ans.append(str(num))
    lv-=1
print(" ".join(ans[::-1]))