[다이나믹 프로그래밍] 1로 만들기 (Python)

이것이 취업을 위한 코딩 테스트다 with 파이썬

---

입력 조건

1. 첫째 줄에 정수 X가 주어진다.

 

출력조건

1. 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

입력예시

26

 

출력예시

3

---

예전에 비슷한 문제를 풀었었는데, 이번에 풀 때 조금 헤맸다. 기본적인 dp문제인데 아직도 풀이방법이 바로 눈에 들어오지 않는다. dp문제는 감을 잃지 않으려면 꾸준히 풀어야할 것 같다.

 

Python code

x=int(input())

dp=[0]*(x+1)

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

print(dp[x])