[BOJ] 1463 1로 만들기

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

<코드설명>

먼저 n을 입력받아주었다. 

for문을 이용하여 2부터 n까지 반복시켜주었다. 

1을 빼줬을 때 횟수 추가를 하기 위해 d[i]=d[i-1]+1을 해주었다.

i가 2로 나눠 떨어질 경우, 원래 수인 d[i]와 d[i//2]+1의 값을 비교하여 더 작은 값을 d에 넣어주었다.  +1은 횟수를 추가해주기 위함이다.

i가 3으로 나눠 떨어질 경우, 원래 수인 d[i]와 d[i//3]+1의 값을 비교하여 더 작은 값을 d에 넣어주었다.  마찬가지로 +1은 횟수를 추가해주기 위함이다. 

이렇게 구한 d[n]을 출력해주었다.

 

 

<실행결과>