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

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

 

SOLUTION

점화식과 다이나믹 프로그래밍을 이용해푼다.

f(x)는 다음과 값 중 최솟값을 가진다.

1) f(x-1) + 1

2) f(x/2) + 1

3) f(x/3) + 1

이 세 함수의 최소 값을 구해주면 된다.

 

재귀함수를 매번 호출하면 시간복잡도가 굉장히 커지므로 다이나믹 프로그래밍 즉, 리스트를 만들어 값을 매번 저장해주는 것이 속도 향상에 도움이 된다.

PYTHON CODE

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 < result[i][0]:
        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=' ')