[백준] #12852 Python

백준 12852번 파이썬

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

아이디어

다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나누어 해결한다 + 해결한 작은 문제들을 배열에 저장하여 나중에 또 필요할 때 쓸 수 있게 한다(메모이제이션)

재귀함수를 사용하는 top-down 방식과 dp를 사용한 bottom-up 방식 두가지로 나뉘는데, 시간 복잡도가 낮고 이해하기 쉬운(이 문제에서는) bottom-up 방식을 사용!
먼저 i가 어떤 수인지 상관 없이 1을 더했을 때의 계산 수를 저장해주고, i가 2나 3으로 나뉘는지의 여부에 따라 (i // 3)의 계산 수 + 1 값과 원래 값 중 작은 값을 택하는 방식으로 진행된다.

전체코드

import sys
input = sys.stdin.readline
N = int(input())

dp = [0, [0, [1]], [1, [2,1]], [1, [3,1]]]
for i in range(4, N+1):
    dp.append([dp[i-1][0] + 1, [i] + dp[i-1][1]])
    if i % 3 == 0 and dp[i//3][0] + 1 < dp[i][0]:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = [i] + dp[i//3][1]

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


print(dp[N][0])
for i in dp[N][1]:
    print(i, end = ' ')

느낀점

dp는 연습이 많이 필요한 알고리즘인 것 같다. 해설을 봐도 이해가 쉽게 되지 않는 풀이가 많다. 특히 큰 문제를 작은 문제로 쪼개는 과정이 아직은 어렵다,,, 연습밖에 답이 없다.