1464 1로 만들기

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

 

✔ 유형 : DP

✔ 문제 풀이: 

정수에 사용할 수 있는 연산은 총 3가지인데, 빠르게 1을 만들려면 세가지 연산을 시행했을 때 값이 가장 작아야 한다.

X라는 수를 1로 만들으려 했을 때,

위 세가지 연산을 시행하면 우선 1번의 연산을 한 것이 된다.

 

DP[X] = 정수 X에 연산을 시행했을 때 1이 되는 최소 연산 수행 횟수

라고 정의할 때

 

다음과 같이 문제를 작게 나눌 수 있다.

DP[X] = 1 + DP[X에 세가지 연산중 하나로 실행한 결과]

와 같게 된다.

 

따라서 X에 세 가지 연산을 실행한 결과 값 중 가장 작은 값을 반영해서

최소 연산 횟수를 저장해 나갈 수 있다.

 

다시 정리해보면 아래 점화식을 세울 수 있다.

 

코드

import sys
N = int(input())

DP = [0 for _ in range(N+1)]

if(N > 1):
    for i in range(2,N+1):    
        DP[i] = 1 + min(DP[i//3]  if i%3 == 0 else 1e9 , DP[i//2] if i%2 == 0 else 1e9, DP[i-1]) 
    
    
print(DP[N])