[Baekjoon 12852 / python / 실버1] 1로 만들기 2

import sys

input = sys.stdin.readline

x = int(input())

d = [0] * (x + 1)

path = ['' for _ in range(x + 1)]

path[1] = '1'

for i in range(2, x + 1):

    d[i] = d[i - 1] + 1

    prev = i - 1

    if i % 3 == 0 and d[i // 3] + 1 < d[i]:

        d[i] = d[i // 3] + 1

        prev = i // 3

   

    if i % 2 == 0 and d[i // 2] + 1 < d[i]:

        d[i] = d[i // 2] + 1

        prev = i // 2

    path[i] = str(i) + " " + path[prev]

print(d[x])

print(path[x])

 

1로 만들기 문제를 업그레이드한 문제이다.  1로 만들기 -> https://yskisking.tistory.com/197

 

문제 자체는 같지만 x가 나눠지는 과정을 추가로 출력해야 한다.

2, 3, 4, 5... x 까지 올라가면서 그때그때 나눠지는 과정을 path 리스트에 기록해 두면 된다.

 

d는 최소연산횟수를 담을 리스트

path는 나눠지는 과정을 담을 리스트이다. 참고로 인덱스 i에 대한 값은 , 숫자 i에 대한 나눠지는 과정이다. 각 인덱스마다 해당 숫자의 나눠지는 과정이 일일이 담겨 있다.

 

 

이번 반복문에서는 d[i]값만 갱신하지 않고 prev 변수에 i의 변화를 함께 담아둔다. 참고로 저번처럼 min을 사용하면 어떤 값이 선택되었는지 다시 한번 확인해야 하기 때문에 조건문에서 d[i//3] + 1 < d[i] 와 같은 과정을 함께 처리했다.

 

d[i]값 갱신이 끝났다면 현재 숫자와 path[prev] 에 담겨있는 나눠지는 과정을 합쳐서 path[i]에 저장한다.

이렇게 하면 문제를 해결할 수 있다.