🔍 Problem

1463 1로 만들기

---

⚡️ 사용한 알고리즘

다이나믹(동적) 프로그래밍

---

📃 Input&Output

---

📒 해결 과정

1️⃣ (N이 10이라고 가정) N이 1부터 5까지 최소연산 횟수를 구해본다.
2️⃣ 1은 0, 2는 1, 3은 1일 것이다.
3️⃣ 문제는 4부턴데 4는 2로 떨어지므로 2로나누면 2 그리고 다시 -1을 빼서 1을 만드므로 "2"이다.
4️⃣ 이렇게 직접 구하다보면 4는 2로나눈 2의 최소연산 횟수에서 +1
5️⃣ 5는 -1을 한 4의 최소연산(값)에서 +1 한다는 성질을 찾아 낼 수 있다.
6️⃣ 하지만 6은 -1과 /2와 /3 세개를 다할 수 있다. 이 때는 이 3개의 경우의 최소값을 찾아서 +1해주면 된다.
7️⃣ 이렇게 N까지 구한다. 구한 값들은 dp배열에 저장해놓고 원하는 값을 dp[N]으로 구한다.

N	최소연산	방법
1	0
2	1
3	1
4	2	4/2=2이고 2에서 최소연산은 1이다. 따라서 f(4) = f(4/2)+1 인 것이다.
5	3	f(5) = f(5-1)+1
6	2	f(6) = min(f(6-1)+1, f(6/2)+1, f(6/3)+1)
7	3	위와 동일한 방법으로 계산가능

---

❗주의점

이전 값의 최선이 현재 값의 최선이라는 것을 기억하자. 그렇기에 항상 최선의 값을 구해주는 수식을 넣어줘야한다.

---

💻 Code

import sys
import math
N=int(sys.stdin.readline())
dp=[0]*(N+1)

dp[1]=0

# dp[i] = 1 + min(dp[i//2], dp[i//3], dp[i-1])
for i in range(2,N+1):
    
    # v1 : dp/3, v2 : dp/2, v3 : dp[i-1]
    v1,v2,v3=math.inf,math.inf,dp[i-1]    
    
    if i%3==0:
        v1=dp[i//3]
    if i%2==0:
        v2=dp[i//2]
    
    dp[i]=1+min(v1,v2,v3)

print(dp[N])

---

🤔 느낀점

1. 굉장히 어려웠던 것이, 이전 값을 하나하나씩 차곡차곡 쌓아간다는 것을 받아들이기가 어려웠다. 물론 직접 하나씩 해봐야 몸에 익겠지만 아직은 많이 풀어봐야할 것 같다. Bottom-up 방식이 처음에는 이해가 되지 않았는데 작은 수에서 시작해, 큰수를 완성해 나간다는 점에서 이런 수식어가 붙은 것이 아닐까 생각된다.
2. 이전 값의 최선이 현재 값이 최선이라는 점으로 보아 그리디 알고리즘과 유사하다는 생각이 들었다.

---

📝 출처

https://www.youtube.com/watch?v=MsU1WeBAf2o