[#알고리즘/Dynamic Programming/[백준]1463번: 1로 만들기(python)]

Question

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

Solution

보통 연산 횟수를 최소화하면서 1로 만드는 방법으로, 가장 큰 수(여기선 3)로 나눌 수 있으면 나누는 것이지 않을까?라고 생각하고 접근한다. 나 또한 3으로 나누기 -> 2로 나누기 -> 1 빼기 순서의 방법으로 접근하였다. 하지만 반례가 존재하였다.

10을 생각해보자. 10을 1로 만드는 방법에는
10 -> 5 -> 4 -> 2 -> 1 과
10 -> 9 -> 3 -> 1 의 두 가지 방법이 있다.
위의 경우 1을 먼저 빼야 연산 횟수가 최소가 되는 케이스다. 이 케이스를 다시 정리하면,

10의 경우

• (5를 1로 만드는 최소 횟수) + 1
• (9를 1로 만드는 최소 횟수) + 1
  둘 중 더 작은 횟수를 선택한다.

그렇다면 12의 경우

• (4를 1로 만드는 최소 횟수) + 1
• (6을 1로 만드는 최소 횟수) + 1
• (11을 1로 만드는 최소 횟수) + 1

이들을 비교한다. 이때 4는 2를 1로 만드는 최소 횟수를 원할 것이고, 6과 11 또한 2를 1로 만드는 최소 횟수를 원할 수도 있다. 따라서 이는 전에 계산한 결과를 기억하여 다시 재활용하는 동적 프로그래밍 방법으로 접근한다.

위를 식으로 나타내면 아래와 같다. 이때 f(x)는 1로 만드는 최소 횟수이다.
f(n) = min(f(n/3), f(n/2), f(n-1)) + 1

즉 f(n)은 n을 3으로 나눈 수, 2로 나눈 수, 1을 뺀 수 각각을 1로 만드는 최소 연산 횟수 중 가장 작은 값에 1을 더한 값이 된다.

Code

x = int(input())

# DP 테이블 초기화 
d = [0] * (x+1)

# DP (Bottom-Up)
for i in range(2, x+1) :  # d[1] = 0 이므로 2부터 x까지
    # 현재의 수에서 1을 빼는 경우 (뒤에 +1은 연산 횟수를 세는 것)
    d[i] = d[i-1] + 1
    # 현재의 수가 2로 나누어 떨어지는 경우
    if i % 2 == 0 :
        d[i] = min(d[i], d[i//2] + 1)
    # 현재의 수가 3으로 나누어 떨어지는 경우
    if i % 3 == 0 :
        d[i] = min(d[i], d[i//3] + 1)
        
print(d[x])