1463. 1로 만들기

import sys
n=int(sys.stdin.readline())
count=0
result=[0]*(n+1)
for i in range(2,n+1):
    result[i]=result[i-1]+1 # 일단 1을 먼저 빼기
    if i%2==0:
        result[i]=min(result[i],result[i//2]+1)
    if i%3==0:
        result[i]=min(result[i],result[i//3]+1)
print(result[-1])

 

n=10일때 result를 출력해보면  [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]이다

1. result=[0,0,0,0,0,0,0,0,0,0]  # result[0]*(n+1)

2. result=[0,0,1,0,0,0,0,0,0,0]  # result[2]=result[1]+1

3. result=[0,0,1,0,0,0,0,0,0,0]  # result[2]=min(result[2],result[1]+1)=min(1,2)=1

4. result=[0,0,1,2,0,0,0,0,0,0]  # result[3]=result[2]+1

5. result=[0,0,1,1,0,0,0,0,0,0]  # result[3]=min(result[3],result[1]+1)=min(2,1)=1

.

.

.

6. result=[0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]