Python) 백준 1463번: dp, 1로 만들기

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

숫자 N이 주어졌을 때, 1로 만드는 최소 연산 횟수를 구하는 문제이다.
1. 3으로 나누어떨어지면, 3으로 나누는 연산
2. 2로 나누어떨어지면, 2로 나누는 연산
3. 1을 빼는 연산

이 문제는 Dynamic Programming(동적 계획법)을 사용하여 해결할 수 있다.

 

import sys

input = sys.stdin.readline

def make_one(n):
    dp = [0] * (n + 1)
    
    for i in range(2, n + 1):        
        if i % 2 == 0:
            a = dp[i // 2] + 1
        else:
            a = float('inf')
            
        if i % 3 == 0:
            a = min(a, dp[i // 3] + 1)
        
        b = dp[i - 1] + 1

        dp[i] = min(a, b)
    
    return dp[n]

N = int(input().strip())
print(make_one(N))

 

 

• 초기값 설정
  • dp[1]은 0으로 설정. 왜냐하면, 숫자 1은 연산이 필요 없기 때문이다.
  • dp[2]부터 값을 계산한다.
• 나누기 연산과 1 빼기 연산
  • 2로 나누어 떨어지는 경우: dp[i // 2] + 1을 계산합니다. 이때 dp[i // 2]는 이미 계산된 값이며, +1은 연산 횟수를 추가하는 것이다.
  • 3으로 나누어 떨어지는 경우: 동일하게 dp[i // 3] + 1을 계산한다.
  • 1을 빼는 경우: dp[i - 1] + 1을 계산한다.
• 최소값 계산
  • 위 세 가지 방법 중 가능한 방법들 중 최소값을 dp[i]에 저장한다.
• 무한대 값 처리
  • 숫자가 2나 3으로 나누어지지 않을 경우를 처리하기 위해 float('inf') 값을 사용하여 해당 조건이 성립하지 않음을 표시다.