[BOJ / Python] 1463번: 1로 만들기

문제: BOJ 1463번

풀이

쉬운 다이나믹 프로그래밍이다. 바텀업으로 배열에 필요한 연산횟수 저장하면서 풀었다.

최종코드

n = int(input())
d = [0] * (n + 1)
for i in range(2, n + 1):
    d[i] = d[i - 1] + 1	#최소 한번은 연산하니까 +1
    if i % 3 == 0:		#3으로 나뉠때 3으로 나뉜 값의 최소연산 값+1과 
    					#기본 d[i]중 어떤 값이 더 작은지 비교해서 넣는다.
        d[i] = min(d[i], d[i // 3] + 1)	
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
print(d[n])