[백준] DP - 1로 만들기

한동안 코테 스터디 하느라 블로그에 코딩 공부 글을 올리지 못했다.. (?모순)

코테 스터디 내용은 차차 올릴 예정이다.

이제 스터디도 끝나서 다시 혼자 공부해야 하는데 열심히 문제풀이 올리면서 꾸준히 공부해야지. :)

 

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

1463번: 1로 만들기

점화식 : d[a] = min ( d[a // 3] +1, d[a // 2] + 1 , d[a - 1] + 1 )

시간 복잡도 : O(N)

a = int(input())

d = [0] * (a + 1)
for x in range(2, a + 1):
    d[x] = d[x - 1] + 1
    if x % 2 == 0:
        d[x] = min(d[x], d[x // 2] + 1)
    if x % 3 == 0:
        d[x] = min(d[x], d[x // 3] + 1)

print(d[a])