[백준] 1463번 1로 만들기 / 파이썬(python)

# 문제 링크

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

# Soultion

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

 

3. 최소계산수를 저장하기 위해 n+1개의 배열을 선언

4. 숫자1은 자기자신이므로 0으로 초기화해준다.

7. 1을 뺀 경우

8. 2로 나눈 경우

10. 3으로 나눈 경우

12. 위의 세가지경우에서 최소값을 구해 1을 더해준다.