[Python] 백준 1463. 1로만들기 (DP)

문제 링크

문제 풀이

1. top_down dp 방식(재귀)
   x 값이 1이 될 때까지 연산 하나씩 함.
   이때, 연산하려는 x 값의 최소 연산 개수에 대한 기록이 있으면, 즉 dp[x]가 있으면 dp[x] 반환.
   없으면 연산 하나를 함.
   그리고 다음 x에 대해서 반복적으로 해줌.
   단, 새로 연산하는 경우, dp에 저장해가면서 함.
2. bottom_up dp 방식
   1부터 x값 까지의 연산 최솟값을 dp에 기록.
   이때, dp[x]는 무조건 dp[x-1] + 1일 수 있다.
   다만 2의 배수이거나 3의 배수일 경우, 위 case가 best case가 아닐 수 있기에
   가능한 다른 경우들을 모두 고려하여, 그 중 최솟값으로 dp[x]를 갱신

Point

• 이 문제의 포인트는 그리디 방식 으로 풀면 안된다는 점.
  - 3으로 나뉜다고 해서 3으로 나눈다거나, 2로 나뉜다고 해서 2로 나누면 안됨. 왜냐하면 어떤 것이 best case인지 알 수 없음.
  - 그래서 항상 x에 할 수 있는 연산들의 모든 경우의 수를 돌려보고, 그 중 최솟값으로 dp 값을 갱신해줘야 함.

코드

import sys

sys.setrecursionlimit(10 ** 6)


def top_down(x):
    if dp[x] or x == 1:
        return dp[x]
    else:
        if x % 3 == 0 and x % 2 == 0:
            if x % 2 == 0:
                dp[x] = min(top_down(x // 3), top_down(x // 2)) + 1
            else:
                dp[x] = min(top_down(x // 3), top_down((x - 1) // 2) + 1) + 1
        elif x % 2 == 0:
            if x % 3 == 1:
                dp[x] = min(top_down(x // 2), top_down(x - 1)) + 1
            elif x % 3 == 2:
                dp[x] = min(top_down(x // 2), top_down(x - 2) + 1) + 1
        else:
            dp[x] = top_down(x - 1) + 1
    return dp[x]


def bottom_up(x):
    for i in range(4, x + 1):
        dp[i] = dp[i - 1] + 1
        if i % 6 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1, dp[i // 2] + 1)
        if i % 3 == 0:
            dp[i] = min(dp[i], dp[i // 3] + 1)
        elif i % 2 == 0:
            dp[i] = min(dp[i], dp[i // 2] + 1)
    return dp[x]


if __name__ == '__main__':
    x = int(input())
    dp = [0] * 1000001
    dp[1], dp[2], dp[3] = 0, 1, 1
    # print(top_down(x))

    print(bottom_up(x))