백준 1463 파이썬(1로 만들기)

문제 : https://www.acmicpc.net/problem/1463 (실버3)

💻 Code

n = int(input())
dp = [0] * (n+1)    # 인덱스는 0부터 시작하므로 n+1개 초기화

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

print(dp[n])

dp[] : 최소연산횟수를 저장하는 list
for i in range(2, n+1) : 2부터 시작하는 이유는 0 과 1은 연산횟수가 0번이기 때문 (0은 고려 안해도됨, 1로 만들기니까)
dp[i] = dp[i-1] + 1
1을 뺐을 경우를 나타냄
ex) i=2 일 경우, dp[i](2)의 연산횟수는 dp[i-1](1)의 연산횟수 보다 1을 뺀 횟수가 1번이 더 더해진거니까
if(i % 2 == 0):, if(i % 3 == 0):
i 즉, 숫자가 2와 3으로 나누어질 경우를 나타냄
이 경우에는 그 전에 (1을 빼는 경우로) 초기화 해놨던 dp[i]와 2나 3으로 나눴을 때의 경우인 dp[i//2]+1, dp[i//3]+1의 연산횟수를 비교하여 최솟값으로 정한다.

🔎 흐름