백준 온라인 저지, 다이나믹프로그래밍 / 1463번: 1로만들기 (파이썬)

문제

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

문제 정의

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

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

접근 방법

- 최적 부분구조와 중복되는 부분 문제이다.
- 최대 30000까지의 숫자가 들어올 수 있으므로, 1부터 4가지의 경우의 수에 대해 한번씩 동작하도록 하여 각 숫자에 대한 인덱스마다 경우의 수의 시행 횟수를 적는다.
- 이때 채운 모든 값에 대해 4가지 경우의 수가 모두 동작하도록 하고, 이후에 채우는 값은 채우지 않도록 한다.

코드

# 접근 방법
# 최적 부분구조와 중복되는 부분 문제이다.
# 최대 30000까지의 숫자가 들어올 수 있으므로, 1부터 4가지의 경우의 수에 대해 한번씩 동작하도록 하여 각 숫자에 대한 인덱스마다 경우의 수의 시행 횟수를 적는다. 
# 이때 채운 모든 값에 대해 4가지 경우의 수가 모두 동작하도록 하고, 이후에 채우는 값은 채우지 않도록 한다.

from collections import deque

x = int(input())

queue = deque([1])

d = [0] * (x+1)
d[1] = 1

while d[x] == 0:
    n = queue.popleft()

    # + 1 연산하기
    if d[n + 1] == 0:
        d[n + 1] = d[n] + 1
        queue.append(n + 1)

    if n * 2 <= x and d[n * 2]="d[n]" 0:
 + 1
 queue.append(n 2)
 if n 3 <="x" 3]="d[n]" 3)
 5 5]="d[n]" 5)

print(d[x] - 1)< />ode>