[Python] 백준 1463 번/1로 만들기/dp

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

1463번: 1로 만들기

🐯 문제 설명 

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

🐯해결 방법

Bottom-up 방식(상향식)을 사용했다.  (동일한 작은 문제 반복 해결)

10인 경우에 10->5->4->2->1 (4번) 보다 10->9->3->1 (3번) 이 더 적다.

그래서 bottom-Up 방식을 사용하여 가장 작은 문제들을 해결해가며 중복되는 계산 값은 저장해놓고 다음 계산에 이용한다.

1을 뺏을 때, 3으로 나눴을 때 , 2로 나눴을 때 모든 경우를 따져 최솟값을 저장한다.

🐯코드

import sys
input=sys.stdin.readline

x=int(input())
dp=[0]*(100001)

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

print(dp[x])