[DP] python 백준 1463번 - 1로 만들기

[DP] python 백준 1463번 - 1로 만들기

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

X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

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

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

풀이

num = int(input())
res = [0,0,1,1]

for i in range(2,num+1):
    res.insert( i, min( res[i//3] if i%3==0 else 1000000, res[i//2] if i%2==0 else 1000000, res[i-1] )+1)

print(res[num])

0 -> 0번 n번째로 맞추기 위해 빈 값

1 -> 0번

2 -> 1번

3 -> 1번

4 -> 2번 (4/2, 2-1)

5 -> 3번 ( 5-1,4/2,2-1 [ 4로 만들고 앞서구한 4가 2니까 1번+2번 = 3번])

6 -> 2번 (6/3 2-1)

7 -> 3번 (7-1,6/3,2-1)

8 -> 3번 8/2 4/2 2-1

9 -> 2번 9/3, 3/3

10 -> 3번 10-1,9/3,3/3

11 -> 4번 11-1,

 

# 6일 때 6/3을 통해 2가 되거나 6/2를 통해 3이 될 수 있다.

# 3가지 방법을 실행 후 그 배열에 들어있는 값 중 최소값으로 계산하면 된다.

점화식 :  f(n) = 1 + min(f(n/3),f(n/2),f(n-1))

 

더하기 1해주는 이유는 한번 연산을 수행한거니까

앞서 계산한 결과 값을 이용한 문제이므로 DP 문제 

 

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