백준 1463번: 1로 만들기

문제

• https://www.acmicpc.net/problem/1463
• 동적 프로그래밍을 활용해 최적해 구하기

기록 포인트

• 동적 프로그래밍 개념을 문제에 적용하는 과정
  • 부분 문제 정의하기
    • 점화식 만들기, 부분 문제의 개수 세기, 각 문제의 선택지 개수 세기
  • 메모 테이블 구성하기
  • 부분 문제의 선후관계(topological order)를 고려해 순서대로 실행하기
• 하향식 vs 상향식
  • 하향식: 현재 문제를 처리하기 위해 부분 문제로 나누어 재귀적으로 내려가는 방식
  • 상향식: 위상적 순서에 따라 부분 문제들을 해결해 올라오는 방식
  • (오름차순/내림차순의 차이가 아니라, 부분 문제들을 푸는 순서의 차이)

접근 방식

• 하향식
  • [1안] 하위 문제 f(x): x에서 N까지 이동하기 위한 최소 횟수
    • 구하려는 답: f(1)
  • [2안] 하위 문제 g(x): x에서 1까지 이동하기 위한 최소 횟수
    • 구하려는 답: g(N)
• 상향식
  • [1안] 하위 문제 f'(x): N에서 x까지 이동하기 위한 최소 횟수
    • 구하려는 답: f'(1)
  • [2안] 하위 문제 g'(x): 1에서 x까지 이동하기 위한 최소 횟수
    • 구하려는 답: g'(N)
  • 상향식으로 풀 때 각 정점에서 본인에게 들어오는 부분 문제들을 확인할 수도 있고, 반대로 각 부분 문제에서 다음 단계의 문제들로 정보를 넘겨줄 수도 있음

제출 답안

import sys
N = int(sys.stdin.readline())

# 1단계: 부분 문제 정의
# - 문제의 정답(solution)이 될 수 있는 부분문제의 선택지는 3개 (나누기 3, 나누기 2, 빼기 1)
# - f(X) = 1 + min(f(X//3), f(X//2), f(X-1))
# - 1부터 N까지의 모든 값이 부분 문제가 될 수 있으며, 부분 문제의 개수 N

# 2단계: memo table 생성
# - 각 부분 문제들의 정답(solution)을 저장하는 메모 테이블 생성
# - 부분 문제의 입력값은 1~N 이므로 인덱스가 부분문제의 입력값을 의미하는 배열 생성
# - (x가 인덱스와 매칭될 수 있도록 배열의 길이를 N+1로 설정)
memo = [None] * (N+1)

# 3단계: 함수 생성 
# - 부분 문제의 선후 관계(topological order)를 고려해 순서대로 실행

# 하향식 
def fn_topdown(x):
    if memo[x]:
        return memo[x]
    if x == 1:
        return 0

    subproblems = [] # 현재 문제 x의 부분문제들
    if x%3 == 0: subproblems.append(x//3)
    if x%2 == 0: subproblems.append(x//2)
    if x > 1: subproblems.append(x-1)

    subscores = [] # 각 부분문제들의 정답
    for p in subproblems:
        subscores.append(fn_topdown(p))

    # 각 부분문제의 정답을 고려해 현재 문제 x에 대한 정답을 선택
    memo[x] = 1 + min(subscores)
    return memo[x]

# 하향식 재구성
def fn_topdown2(x):
    if memo[x]:
        return memo[x]
    if x == 1:
        return 0

    min_subscore = float("inf")
    if x%3 == 0:
        min_subscore = min(min_subscore, fn_topdown2(x//3))
    if x%2 == 0: 
        min_subscore = min(min_subscore, fn_topdown2(x//2))
    if x > 1:
        min_subscore = min(min_subscore, fn_topdown2(x-1))

    # 각 부분문제의 정답을 고려해 현재 문제 x에 대한 정답을 선택
    memo[x] = 1 + min_subscore
    return memo[x]  

# 상향식
from collections import deque
def fn_bottomup(x):
    memo = [None] * (N+1)
    memo[1] = 0
    frontier = deque([1])
    while not memo[x] and frontier:
        v = frontier.popleft() # v 는 subproblem
        subscore = memo[v] # subsccore는 부분문제 v의 정답
        for next_v in [v*3, v*2, v+1]: # next_v 는 v에서 간선으로 이어진 다음 subproblem
            if next_v == x:
                memo[next_v] = subscore + 1
                break
            elif next_v < N+1:
                memo[next_v] = subscore + 1
                frontier.append(next_v)
        # print(memo)                
    return memo[x]

# 상향식 재구성
def fn_bottomup2(x):
    memo = [None] * (N+1)
    memo[1] = 0
    for i in range(2, N+1):
        min_subscore = float("inf")
        if memo[i-1] != None:
            min_subscore = min(min_subscore, memo[i-1]) 
        if i%2 == 0 and memo[i//2] != None:
            min_subscore = min(min_subscore, memo[i//2]) 
        if i%3 == 0 and memo[i//3] != None:
            min_subscore = min(min_subscore, memo[i//3]) 
        memo[i] = min_subscore + 1
    return memo[x]

# 4단계: 본래의 문제 해결
# print(fn_topdown2(N))
print(fn_bottomup2(N))