[DP] 백준 12852번 “1로 만들기 2” Python 풀이

문제 링크

• https://www.acmicpc.net/problem/12852

풀이

• DP 테이블과 점화식을 사용해 해결할 수 있습니다.
• f(x)는 아래 세 가지 값들 중 최솟값이 됩니다.
  1. f(x-1) + 1
  2. x가 2로 나눠지는 경우, f(x//2) + 1
  3. x가 3으로 나눠지는 경우, f(x//3) + 1
• 뒤에 1을 더하는 이유는, 이전 경우의 수로부터 +1 이 되기 때문입니다.
• 따라서, f(2)부터 f(N)까지 위의 점화식을 사용해 DP 테이블을 채워나가면 됩니다.
• 또한, 리스트 안에 또 리스트를 넣어, f(x)가 어떤 수들을 거쳐왔는지를 저장해 나가면 됩니다.
• 따라서, DP 테이블은 아래와 같은 형식으로 채워지게 됩니다.
  • f(0) = [0, []]
  • f(1) = [0, [1]]
  • f(2) = [1, [1, 2]]
  • f(3) = [1, [1, 3]]
  • …
  • f(10) = [3, [1, 3, 9, 10]]

코드

import sys

n = int(sys.stdin.readline())

# DP 테이블 (x를 만드는 최소 연산의 수, [x를 최소 연산으로 만드는 방법])
dp = [[0, []] for _ in range(n+1)]

# DP 테이블에 f(1)의 경우를 초기화
dp[1][0] = 0
dp[1][1] = [1]

for x in range(2, n+1):

    # 먼저, f(x-1) + 1를 사용해 DP 테이블 채우기
    dp[x][0] = dp[x-1][0] + 1
    dp[x][1] = dp[x-1][1] + [x]

    # 이후, x가 2로 나눠지는 경우, 
    if (x % 2 == 0):
        # f(x//2) + 1과 기존 DP 테이블의 값을 비교해, 최솟값으로 변환
        if (dp[x][0] > dp[x//2][0] + 1):
            dp[x][0] = dp[x//2][0] + 1
            dp[x][1] = dp[x//2][1] + [x]

    # 이후, x가 3으로 나눠지는 경우, 
    if (x % 3 == 0):
        # f(x//3) + 1과 기존 DP 테이블의 값을 비교해, 최솟값으로 변환
        if (dp[x][0] > dp[x//3][0] + 1):
            dp[x][0] = dp[x//3][0] + 1
            dp[x][1] = dp[x//3][1] + [x]

# x를 만드는 최소 연산의 수
print(dp[n][0])
# x를 최소 연산으로 만드는 방법
for i in dp[n][1][::-1]:
    print(i, end=" ")