백준 문제 중 1463번, DP, ‘1로만들기’

백준 문제 중 1463번

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

문제

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

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

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

입력

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

출력

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

---

풀이

다이나믹 프로그래밍을 처음 접해 보는 문제였다. 다이나믹 프로그래밍에 대해서는 전혀 지식이 없어서 책을 보고 학습한뒤 메모이제이션, 타뷸레이션등의 방법론들을 학습했는데 꽤나 흥미로웠다.

코드의 논리를 대충 설명 하자면, 1까지 가는 최소의 값을 반환하는 함수를 C(n)이라 하자
그러면 C(n) = min(C(n-1),C(n/2),C(n/3))+1 의 관계를 만족한다. 예를 들어 n=10일때의 C(10)은 C(9),C(5),C(10/3) 으로 이동 하는데 +1을 소모하고 이 세개중 최소값을 고르기만 하면 그값에 1을 더한게 C(10)의 최소가 되기 때문이다.

코드로 작성해보면 다음과 같다.

from collections import defaultdict
import math

n = int(input())

 # 초기값 설정
dp = defaultdict(int)
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 1

def one(n:int)->int:

     # 만약 dp[n]의 값이 이미 존재한다면 바로 리턴
    if dp[n]:
        return dp[n]

     # 4~n까지 진행
    for i in range(4,n+1):

         # min연산을 위해 x,y에 무한대 설정
        x,y = math.inf,math.inf

         # i가 2로 나누어지거나 3으로 나누어진다면 
         # x,y에 각각 C(n/2), C(n/3) 대입
        if i%2==0: x = dp[i//2]
        if i%3==0: y = dp[i//3]

         # C(n-1)을 나타내는 dp[n-1]대입
        z = dp[i-1]

         #C(n) = min(C(n/2), C(n/3), C(n-1)) +1
        dp[i] = min(x,y,z)+1

    return dp[n]

print(one(n))

1
0

추가적으로 dp를 함수 밖에 설정하여 여러번 함수를 호출하게 된다면 미리 계산했던 dp의 값을 이용할 수 있어 더 빠르게 해결할 수 있게끔 했다.

배운점

다이나믹 프로그래밍의 기초에 대해 알 수 있었다.