[알고리즘] 다이나믹 프로그래밍 - 1로 만들기/개미 전사/바닥 공사/효율적인 화폐 구성

다이나믹 프로그래밍(DP, Dynamic Programming)은 큰 문제를 작은 문제로 나누어 푸는 방법론이다. 이번 글에서는 대표적인 DP 문제 세 가지를 정리하고, 해결 방법을 알아보자.

1. 1로 만들기

문제 설명

정수 X가 주어졌을 때, X에 사용할 수 있는 연산은 다음과 같다.
1. X에서 1을 뺀다.
2. X가 2로 나누어떨어지면 2로 나눈다.
3. X가 3으로 나누어떨어지면 3으로 나눈다.
4. X가 5로 나누어떨어지면 5로 나눈다.

이 연산을 이용하여 X를 1로 만들 때 필요한 최소 연산 횟수를 구하라.

해결 방법

각 숫자에 대해 가능한 모든 연산을 고려하여 최적해를 찾는다.

• 예를 들어, f(6)을 생각해보면 가능한 연산은 다음과 같다.

  1. f(5) (1을 뺀 경우)
  2. f(3) (2로 나눈 경우)
  3. f(2) (3으로 나눈 경우)

• 따라서 최적해는 다음과 같이 표현할 수 있다.

  dp[i] = min(dp[i−1] + 1, dp[i//2] + 1, dp[i//3] + 1, dp[i//5] + 1)

코드 구현

x = int(input())
d = [0] * 30001

for i in range(2, x+1):
  d[i] = d[i - 1] + 1
  if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1)
  if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1)
  if i % 5 == 0:
    d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

---

2. 개미 전사

문제 설명

N개의 식량 창고가 있다. 개미 전사는 인접한 두 개의 식량 창고를 털 수 없다. 최대한 많은 식량을 털었을 때의 값을 구하라.

해결 방법

• i번째 식량창고를 털지 말지를 선택한다.
• 두 가지 경우가 존재한다.
  1. (i-2)번째 창고까지 털고 i번째 창고를 터는 경우
  2. (i-1)번째 창고까지 털고 i번째 창고를 털지 않는 경우
• 따라서 점화식은 다음과 같이 정리할 수 있다.

  dp[i] = max(dp[i-2] + a[i], dp[i-1])

코드 구현

n = int(input())
a = list(map(int, input().split()))

d = [0] * 100
d[0] = a[0]
d[1] = max(a[0], a[1])

for i in range(2, n):
  d[i] = max(d[i-2] + a[i], d[i-1])

print(d[n-1])

---

3. 바닥 공사

문제 설명

가로 길이 N, 세로 길이 2인 바닥을 채우는 방법의 개수를 구하라. 사용할 수 있는 타일은 1×2, 2×1, 2×2 타일이다.

해결 방법

• 바닥을 채우는 방법을 고려해보면 다음과 같다.
  1. (n-1)까지의 바닥이 채워져 있다면, 1×2 타일을 하나 추가하는 경우 (1가지 방법)
  2. (n-2)까지의 바닥이 채워져 있다면, 2×1 두 개 또는 2×2 하나를 추가하는 경우 (2가지 방법) -> 1×2의 경우 1번에서 고려했기 때문에 여기선 제외한다.
• 따라서 점화식은 다음과 같이 도출할 수 있다.

  dp[n] = dp[n-1] + 2 * dp[n-2]

코드 구현

n = int(input())
d = [0] * 1001

d[1] = 1
d[2] = 3

for i in range(3, n+1):
  d[i] = (d[i-1] + 2 * d[i-2]) % 796796

print(d[n])

---

4. 효율적인 화폐 구성

문제 설명

N가지 종류의 화폐가 있다. 이 화폐들을 이용하여 합이 M원이 되도록 만들려고 한다. 이때, 사용한 화폐의 개수가 최소가 되도록 하려 한다.

예를 들어, N = 2, M = 15이고, 화폐의 종류가 2원과 3원이라고 가정하자. 이때, 다음과 같이 5개의 화폐를 사용하면 15원을 만들 수 있다.

• 3원을 5개 사용 (3 × 5 = 15)

하지만 2원과 3원을 적절히 사용하면 더 적은 개수의 화폐를 사용할 수도 있다. 최소 개수의 화폐를 사용하는 방법을 찾는 프로그램을 작성하시오.

해결 방법

이 문제는 다이나믹 프로그래밍(DP)을 이용하여 해결할 수 있다. DP 테이블을 활용하여 다음과 같은 점화식을 적용한다.

DP 테이블 초기화

1. DP 테이블을 M+1 크기로 할당하고, 큰 값(예: 10001)으로 초기화한다.
2. dp[0] = 0으로 설정하는데, 이는 아무 화폐도 사용하지 않아도 0원을 만들 수 있기 때문이다.
   • 예를 들어, 0원을 만들기 위해서는 동전을 하나도 사용하지 않으면 된다. 따라서 초기값을 0으로 설정한다.

점화식 도출 과정

1. 특정 금액 K를 만들기 위해서는, 해당 금액 K에서 한 가지 화폐 단위 C를 뺀 금액 K - C를 만드는 최소 개수에 화폐 하나를 추가하면 된다.

2. 즉, dp[K]는 dp[K - C] + 1이 될 수 있으며, 여러 경우 중 최소 개수를 선택해야 한다.

3. 따라서 점화식은 다음과 같이 표현할 수 있다.

   dp[K] = min(dp[K], dp[K - C] + 1)

4. 단, dp[K - C]가 초기값(예: 10001) 그대로라면, K - C원을 만들 방법이 없다는 뜻이다. 즉, 이전 금액을 만들 수 있어야 현재 금액도 만들 수 있기 때문에 이 경우 dp[K]를 갱신하지 않는다.

점화식 적용 과정

1. DP 테이블을 M 크기만큼 할당하고, dp[0]을 0으로 초기화한다.
2. 모든 화폐 단위를 하나씩 확인하면서 해당 화폐로 만들 수 있는 금액들을 갱신한다.
3. 각 화폐 단위마다 dp[K] 값을 점화식에 따라 갱신해 나간다.

예제 설명 (N = 3, M = 7, 화폐 단위 = 2, 3, 5)

초기 DP 테이블 (M = 7)

[0, 10001, 10001, 10001, 10001, 10001, 10001, 10001]

1. 화폐 2원을 사용하여 갱신 (2원 단위로 최소 개수 갱신):

[0, 10001, 1, 10001, 2, 10001, 3, 10001]

2. 화폐 3원을 사용하여 갱신 (3원 단위로 최소 개수 갱신):

[0, 10001, 1, 1, 2, 2, 3, 3]

3. 화폐 5원을 사용하여 갱신 (5원 단위로 최소 개수 갱신):

[0, 10001, 1, 1, 2, 1, 2, 2]

최종적으로 dp[7] = 2가 되어, 최소 2개의 화폐(2원 + 5원)로 7원을 만들 수 있다.

코드 구현

# 입력 받기
n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]

# DP 테이블 초기화
dp = [10001] * (m + 1)
dp[0] = 0  # 0원을 만들기 위해 필요한 동전 개수는 0개

# 다이나믹 프로그래밍 진행
for coin in coins:
    for i in range(coin, m + 1):
        if dp[i - coin] != 10001:  # 만들 수 있는 경우만 갱신
            dp[i] = min(dp[i], dp[i - coin] + 1)

# 결과 출력
print(dp[m] if dp[m] != 10001 else -1)

시간 복잡도 분석

이 알고리즘은 화폐의 개수 N과 목표 금액 M에 대해 O(NM)의 시간 복잡도를 가진다. N의 최대값이 100이고, M의 최대값이 10,000이므로 최악의 경우 1,000,000번의 연산이 이루어지며, 이는 충분히 해결 가능한 범위이다.

---

결론

이렇게 다이나믹 프로그래밍을 활용하여 문제를 해결할 수 있다. 핵심은 최적 부분 구조와 중복되는 부분 문제를 인식하고 점화식을 세우는 것이다. 문제를 해결할 때 위 과정을 충분히 연습하면, DP 문제를 쉽게 해결할 수 있을 것이다.