[백준] 1463 1로 만들기 (파이썬)

알고리즘 아이디어

• 동적계획법을 활용한다

1. n이 1이면 연산은 0번, 2나 3이면 연산은 1번이다

2. 3가지 경우의 수 (빼기 1, 나누기 2, 나누기 3) 중 가능한 경우를 모두 비교해 최소 연산 횟수를 구한다

코드

# 점화식
# f(i) = 0    if n = 1
#      = 1    if n = 2 or n = 3
#      = min(f(i/3), f(i/2), f(i-1)) + 1

#DP Bottom-up
def countOperation(n):
	table = [0] * (max(n+1, 5))
	table[2] = table[3] = 1
	for i in range(4, n+1):
		table[i] = table[i-1] + 1
		if i%3 == 0:
			table[i] = min(table[i], table[i//3]+1)
		if i%2 == 0:
			table[i] = min(table[i], table[i//2]+1)
	return table[n]

n = int(input())
print(countOperation(n))