동적 계획법(Dynamic Programming)이란?

동적 계획법(DP)은 복잡한 문제를 여러 개의 간단한 부분 문제로 나누어 해결하는 알고리즘 설계 기법입니다. 핵심은, 각 부분 문제의 해를 한 번만 계산하고 그 결과를 **메모리 공간에 저장**하여, 동일한 부분 문제가 다시 등장할 때 저장된 결과를 그대로 사용하는 것입니다. 이를 통해 중복 계산을 획기적으로 줄여 성능을 최적화합니다.

DP가 성립하기 위한 두 가지 핵심 조건

  1. 최적 부분 구조: 전체 문제의 최적해가 그 부분 문제들의 최적해로부터 구해질 수 있어야 합니다. 즉, 부분 문제의 최적해가 전체 문제의 최적해에 기여합니다.
  2. 중복되는 부분 문제: 동일한 부분 문제가 반복적으로 나타나야 합니다.


DP를 푸는 핵심 원리

DP 문제는 보통 다음과 같은 순서로 접근하여 해결할 수 있습니다.

  1. DP 테이블 정의: 문제의 상태를 나타내는 배열(DP 테이블)을 정의합니다. D[i]가 무엇을 의미하는지 명확히 해야 합니다. (예: D[i] = i를 1로 만드는 데 필요한 최소 연산 횟수)

  2. 점화식 도출: DP 테이블의 값들 사이의 관계식(점화식)을 찾습니다. 즉, D[i]를 D[i-1], D[i/2] 등 더 작은 부분 문제의 해를 이용하여 어떻게 계산할 수 있는지 정의합니다.

  3. 초기값 설정: 점화식이 시작될 수 있는 가장 작은 단위의 값(초기값 또는 기저 상태)을 설정합니다. (예: D[1] = 0)


예제: 백준 1463번 “1로 만들기”

문제 설명

  • 정수 X가 주어졌을 때, 다음 세 가지 연산을 적절히 사용하여 1을 만들려고 한다.

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

  • 위의 연산을 사용하는 횟수의 최솟값을 출력하라.


코드 구현

import sys
input = sys.stdin.readline

x = int(input())
d = [0] * (x + 1)  # DP 테이블 (d[i]는 i를 1로 만드는 최소 연산 횟수)

# Bottom-up 방식으로 2부터 x까지 테이블을 채워나감
for i in range(2, x + 1):
    # 1. '1을 빼는' 연산은 항상 가능
    d[i] = d[i - 1] + 1
    
    # 2. '2로 나누는' 연산이 가능하다면, 기존 값과 비교하여 더 작은 값 선택
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
        
    # 3. '3으로 나누는' 연산이 가능하다면, 기존 값과 비교하여 더 작은 값 선택
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)

print(d[x])


코드 분석

  1. DP 테이블 정의
d = [0] * (x + 1)

→ (원리 1 적용) d라는 이름의 DP 테이블을 생성합니다. 여기서 d[i]는 **“정수 i를 1로 만드는 데 필요한 연산 횟수의 최솟값”**을 의미합니다. 우리의 최종 목표는 d[x]를 구하는 것입니다.

  1. 점화식을 통한 테이블 채우기 (Bottom-up) for 루프는 i=2부터 x까지 올라가며 d 테이블을 채워나갑니다. 이 방식을 **Bottom-up(상향식)**이라고 하며, 가장 작은 문제부터 차례로 해결하여 최종 문제에 도달합니다.
# 1을 빼는 경우
d[i] = d[i - 1] + 1

→ (원리 2 적용: 점화식의 기초) d[i]를 계산하기 위한 첫 번째 후보입니다. i를 1로 만드는 방법 중 하나는, 먼저 i-1을 1로 만든 후(d[i-1]회의 연산) i에서 1을 빼는 연산(+1회)을 추가하는 것입니다. 따라서 d[i-1] + 1이 d[i]의 후보가 됩니다.

# 2로 나누는 경우
if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1)

→ i가 2로 나누어 떨어진다면, 또 다른 방법이 존재합니다. 바로 i/2를 1로 만든 후(d[i//2]회의 연산) i를 2로 나누는 연산(+1회)을 하는 것입니다. 이 결과(d[i//2] + 1)를 기존 d[i] 값(1을 뺐을 때의 경우)과 비교하여 더 작은 값(최솟값)을 선택합니다. 이것이 바로 최적 부분 구조 원리가 적용되는 부분입니다.

# 3으로 나누는 경우
if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1)

→ 3으로 나누는 경우도 마찬가지입니다. d[i//3] + 1과 현재까지 계산된 d[i]의 최솟값을 비교하여 갱신합니다.

결과적으로, d[i]는 다음 세 가지 값 중 가장 작은 값으로 결정됩니다.

  • d[i-1] + 1
  • d[i/2] + 1 (i가 2의 배수일 때)
  • d[i/3] + 1 (i가 3의 배수일 때)

이것이 이 문제의 점화식입니다.

  1. 최종 결과 출력
print(d[x])