[python 파이썬]백준 1463번 : 1로 만들기

DP 좋은 문제 추천

https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C

문제

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

풀이

문제 풀이 1일차 첫 고비였다. 솔직히 작심일일도 못가서 그만두고싶었다. 혼자 못풀고 다른 코드 참고하고 풀었는데도 이해가 잘 가지 않는다. 다시 와서 봐야지

n = int(input())

dp=[0 for _ in range(n+1)]

for i in range(2,n+1):
 dp[i] = dp[i-1] + 1
 if i % 3 == 0:dp[i] = min(dp[i//3]+1, dp[i])
 elif i % 2 == 0:dp[i] = min(dp[i//2]+1, dp[i])

print(dp[n])