[BOJ/python] 1463: 1로 만들기

문제

✔️ silver 3
다이나믹 프로그래밍

문제 흐름

규칙이 주어져있고 이를 반복해서 특정 값을 구하는 흐름! => DP
초기값인 1이 0이 되도록 하고, 그 뒤는 규칙들을 적용시켰을 때 최솟값을 가지도록 했다.

코드

# 1로 만들기
# dp

import sys
input = sys.stdin.readline

def dp (n: int):
    memo = [0 for i in range(n+1)]
    if n == 1:
        return 0
    elif 1 < n <= 3:
        return 1
    x = 2
    while x <= n:
        case_1 = memo[x // 3] if x % 3 == 0 else float('inf')
        case_2 = memo[x // 2] if x % 2 == 0 else float('inf')
        case_3 = memo[x - 1]
        memo[x] = min(case_1, case_2, case_3) + 1
        x += 1
    # print(memo)
    return memo[n]

if __name__ == "__main__":
    n = int(input())
    result = dp(n)
    print(result)

마무리

DP와 백트래킹은 왜인지 모르겠지만 항상 헷갈린다.
둘 다 빠른 시일 내에 정리해야겠다.!!!