[백준 1463 : PYTHON] 1로 만들기

문제 풀기 : 1463번

1463번: 1로 만들기

문제

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

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

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

 

문제풀이

•  

1로 만들기 위한 연산의 최소 사용 횟수를 구하는 문제이다.

하나의 숫자에 3가지 연산을 계속해서 수행해야 하기 때문에 중복연산이 동반되어 DP로 푸는 것이 좋다.

최적의 연산 횟수를 저장하는 DP 테이블을 생성한다.

현재의 정수X에 연산이 수행될 때마다 DP 테이블을 갱신해주는데 이 때 고려해야할 점이 있다.

 

세 가지 연산 중 1을 빼는 연산은 어떠한 조건이 필요없지만,

2 또는 3으로 나눌 때는 반드시 나누어 떨어질 때만 수행해야 한다.

 

점화식을 작성해보면

dp[i] = min( dp[i - 1], dp[i/2], dp[i/3] ) + 1

 

각각의 연산을 수행했을 때의 가장 적은 연산의 dp(최적의 경우의 수) 값을 찾고 연산 횟수 1을 더해준다.

 

전체코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1000001

for i in range(2, n+1):
    # 1을 빼는 연산
    dp[i] = dp[i-1] + 1
    
    # 2로 나누어 떨어질 때 2로 나누어 연산하고 기존의 dp[i]의 값 중 작은 것을 최적의 횟수로 저장
    # 자연스레 -1한 연산과 min 비교를 하게됨
    if i % 2 == 0 :
        dp[i] = min(dp[i], dp[i//2] + 1)

    # 3로 나누어 떨어질 때 3으로 나누어 연산하고 기존의 dp[i]의 값 중 작은 것을 최적의 횟수로 저장
    # 자연스레 /2한 연산과 min 비교를 하게됨
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)

print(dp[n])