1로 만들기

1. 문제 설명

출처 : 이코테2021

---

2. 문제 조건

---

3. 문제 해결 아이디어

• 피보나치 수열 문제를 도식화한 것처럼 함수가 호출되는 과정을 그림으로 그리면 이와같다.
  • 최적 부분 구조와 중복되는 부분 문제를 만족

 

• 1을 빼는 연산을 제외하고는 해당 수로 나누어떨어질 때에 한해 점화식을 적용할 수 있다.

---

4. 답안

x = int(input())

d = [0] * 30001

#바텀 업방식
for i in range(2, x + 1):
    #현재의 수에서 1을 빼는 경우
    d[i] = d[i - 1] + 1
    #현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    #현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)
    #현재의 수가 5으로 나누어 떨어지는 경우
    if i % 5 == 0:
        d[i] = min(d[i], d[i // 5] + 1)
        
print(d[x])

• x가 30000만까지 들어올 수 있으므로 DP테이블은 30001까지 초기화한다.
• 4가지중 가장 작은 수를 찾아서 더할 것 이므로 매번 min함수로 호출하여 바꾼다.

#출력
26
3