백준 1463. 1로 만들기

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

1463번: 1로 만들기

동적 프로그래밍은 뭔가 감 잡은 것 같다 하면 또 신기한 문제가 튀어나오네..

기본적으로 작은 값부터 쌓아올리는 시도는 했는데 카운트 자체를 셀 생각이 쉽게 나지 않았다.

 

n = int(input())

d = [0] * (n + 1)
for i in range(2, n+1):
	d[i] = d[i-1] + 1 #1을 뺀 경우는 d[i-1]연산 + 1번 연산
	if i%3 == 0:
		d[i] = min(d[i], d[i//3] + 1) #더 작은 게 필요하기 때문에 1을 빼는 연산과 나머지 연산 비교
	if i%2 == 0:
		d[i] = min(d[i], d[i//2] + 1)
print(d[n])