백준|1464번|1로 만들기

문제설명
정수 N을 세 가지 연산 방식을 이용하여 1로 만드는 최소한의 연산횟수를 출력하는 문제입니다.

연산의 종류
1. N이 3으로 나누어 떨어지면, 3으로 나눈다.
2. N이 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

작동 순서
1. 숫자 N을 입력받는다.
2. 숫자 N이 2 또는 3의 배수가 아닌 경우 나누기는 불가능하므로 1을 빼는 방법밖에 없다. 그러므로 N을 만드는 최소한의 연산횟수는 이전 숫자를 만드는 수행횟수+1이다.
3. 숫자 N이 2의 배수인 경우 2로 나눌수 있으므로 N을 만드는 최소한의 연산횟수는 N/2을 만드는 연산횟수+1이다.
4. 숫자 N이 3의 배수인 경우 3으로 나눌수 있으므로 N을 만드는 최소한의 연산횟수는 N/3을 만드는 연산횟수+1이다.
5. 모든 연산이 완료되면 해당 숫자를 만드는 데 필요한 연산의 회수를 출력한다.

소스코드

N = int(input())
dp = [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[int(i/2)]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[int(i/3)]+1)
print(dp[N], end="")