[파이썬] 백준 12852 : 1로 만들기 2

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

12852번: 1로 만들기 2

숫자 N이 주어졌을 때 세가지 연산을 해가며 1을 만드는 카운트를 출력하고 거쳐온 수들 또한 출력하는

문제이다. 맨 처음에 그냥 리스트에 계속 넣어서 리스트에 1이 있으면 출력하는 식으로 했지만 시간이 오래걸려 다른분이 푼 방식을 사용했다.

 

https://claude-u.tistory.com/349

#298 백준 파이썬 [12852] 1로 만들기 2 - 다이나믹 프로그래밍

 

f(x)가

1) f(x-1) + 1

2) f(x/2) + 1

3) f(x/3) + 1

이 세 값중 최소를 갖는다는 방식이다. 뒤에 1을 더하는 이유는 x가 x-1,x/2,x/3로 가는 과정에서

count +=1이 되기 때문이다.

또한 리스트 안에 또 리스트를 넣어 거쳐온 수들을 저장한다.

 

 

 

 

N = int(input())

 

result = [[0, []] for _ in range(N + 1)] #[최솟값, 경로 리스트]

result[1][0] = 0 #최솟값

result[1][1] = [1] #경로를 담을 리스트

 

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

    

    #f(x-1) + 1   

    result[i][0] = result[i-1][0] + 1

    result[i][1] = result[i-1][1] + [i] #경로이므로 지나온 리스트를 추가해줌

    

    #f(x//3) + 1   

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

        result[i][0] = result[i//3][0] + 1

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

 

    #f(x//2) + 1   

    if i % 2 == 0 and result[i//2][0] + 1 < min(result[i][0],result[i//3][0] + 1 ):

        result[i][0] = result[i//2][0] + 1

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

        

print(result[N][0])

for i in result[N][1][::-1]: #뒤집은 뒤 출력

    print(i, end=' ')