[Python] 백준 1463: 1로 만들기

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

1463번: 1로 만들기

DP 개념 연습하기 괜찮은 문제. 다른 DP 문제와 마찬가지로 점화식을 만들어 보았다.

DP 문제는 개인적으로 풀이가 너무 짧아서 허탈할 때가 있다... 익숙해지기 전까지 규칙 찾고 그 부분을 토대로 메모리에 저장하는 것을 목표로 하는 중!

N = int(input())
lst = [0]*(N+1)

for i in range(2,N+1):
    if i % 6 == 0: #6의 배수인 경우
        lst[i] = min(lst[i//2], lst[i//3], lst[i-1])+1
    elif i % 3 == 0: #3의 배수인 경우
        lst[i] = min(lst[i//3], lst[i-1])+1
    elif i % 2 == 0:
        lst[i] = min(lst[i//2], lst[i-1])+1
    else:
        lst[i] = lst[i-1] + 1
print(lst[N])