[이코테] DP : 1로 만들기

문제

정수 X가 주어질 때 X가 5, 3, 2로 나누어 떨어지면 나눌 수 있고 -1을 빼는 연산을 가질 때 최소한의 연산을 1을 만드는 횟수를 구하는 문제

✍️ 나의 풀이

---

• -1은 따로 무조건 실행된다.
• 나머지는 나누어 떨어진다는 조건이 필요하다.
• 전에 구했던 값들이 다시 쓰인다는 것을 눈치채야 한다.

🛠 나의 코드

---

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

print(d[x])

📝 정리

---

🎈 참고

---

• 이것이 취업을 위한 코딩테스트다 with python