(DP) 백준 1463번 1로 만들기

내가 처음에 푼 방식의 코드

n = 10
count = 0

def solution(i):

    global count

    if i <= 1:
        return False

    count += 1

    if i > 3:
        if i % 3 != 0:
            solution(i-1)

        else:
            solution(i//3)

    else:
        return

solution(n)
print(count)

나처럼 코드를 작성하면 DP를 잘못 이해한 것이다. DP는 점화식처럼 처음부터 수를 구해서 넣어보는 방식으로 풀어야한다고 한다.

참고

정답코드

n = int(input())

dp = [0] * (n+1) # 메모이제이션, 값을 기록하기 위한 공간

for i in range(2, n+1): # 어차피 1은 자기 자신이므로 2부터 시작
    dp[i] = dp[i-1] + 1 # 현재 값은 전 값의 +1이다. (마지막 조건에서 1을 빼기 때문에)

	# 다만 2와 3으로 나누어 떨어질 경우에는 2와 3으로 나눈 값, 즉 전 값에다가 1을 더한 값 (전 값이므로)과 기존에 정의했던 값과 비교해서 작은 값을 정답으로 한다.
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])