여러 개의 대상을 순서대로 처리할 때, 바로 이전 선택과 현재 선택이 서로 영향을 주는 문제가 있습니다.
예를 들어 인접한 구역에는 같은 색을 사용할 수 없고, 각 구역마다 색을 선택하는 비용이 다르다면 어떻게 해야 할까요?
단순히 매번 가장 싼 색을 고르면 될 것 같지만, 바로 옆 구역과 색이 겹치면 안 되기 때문에 전체를 보고 판단해야 합니다.
이번 글에서는 이런 조건에서 최소 비용을 구하는 DP 문제를 정리해보겠습니다.
문제
한 전시관에는 일렬로 이어진 여러 개의 구역이 있습니다.
각 구역은 여러 색 중 하나로 칠할 수 있습니다.
다만 규칙이 하나 있습니다.
바로 붙어 있는 두 구역은 같은 색을 사용할 수 없습니다.
각 구역을 특정 색으로 칠하는 비용이 2차원 배열로 주어질 때, 모든 구역을 규칙에 맞게 칠하는 최소 비용을 구하세요.
입력 형태
비용 배열 costs가 주어집니다.
costs[i][j]
의 의미는 다음과 같습니다.
i번째 구역을 j번째 색으로 칠하는 비용
예를 들어 색이 3개라면 각 행은 이런 의미를 가집니다.
[빨강 비용, 파랑 비용, 초록 비용]
예시
costs = [
[7, 3, 8],
[6, 5, 2],
[4, 9, 1]
]
이 예시는 구역이 3개, 색이 3개인 경우입니다.
| 구역 | 색 0 | 색 1 | 색 2 |
|---|---|---|---|
| 0 | 7 | 3 | 8 |
| 1 | 6 | 5 | 2 |
| 2 | 4 | 9 | 1 |
가능한 선택 중 하나는 다음과 같습니다.
0번 구역 → 색 1, 비용 3
1번 구역 → 색 2, 비용 2
2번 구역 → 색 0, 비용 4
총 비용은 다음과 같습니다.
3 + 2 + 4 = 9
따라서 이 경우 최소 비용은 9입니다.
왜 단순히 가장 싼 색만 고르면 안 될까?
각 구역에서 가장 싼 색만 고르면 문제가 생길 수 있습니다.
예를 들어 어떤 구역에서 가장 싼 색이 이전 구역과 같다면, 그 선택은 규칙에 맞지 않습니다.
즉, 현재 구역의 선택은 바로 이전 구역의 색에 영향을 받습니다.
이런 문제는 DP로 접근하기 좋습니다.
DP로 생각하기
dp[i][j]를 이렇게 정의하겠습니다.
dp[i][j] = i번째 구역을 j번째 색으로 칠했을 때의 최소 누적 비용
여기서 중요한 점은 i번째 구역을 j색으로 칠한다고 이미 정해두는 것입니다.
그러면 바로 이전 구역은 j와 다른 색이어야 합니다.
즉, 이전 구역에서 j가 아닌 색으로 끝나는 경우 중 최소 비용을 골라야 합니다.
점화식
현재 구역을 j 색으로 칠하려면,
이전 구역은 j가 아닌 색이어야 합니다.
따라서 점화식은 이렇게 됩니다.
dp[i][j] = costs[i][j] + min(dp[i - 1][다른 색])
조금 더 풀어 쓰면:
현재 색 비용 + 이전 구역에서 현재 색과 다른 색을 선택한 최소 비용
코드
def min_paint_cost(costs):
if not costs:
return 0
n = len(costs)
k = len(costs[0])
dp = [[0] * k for _ in range(n)]
for color in range(k):
dp[0][color] = costs[0][color]
for area in range(1, n):
for color in range(k):
best_previous = float("inf")
for prev_color in range(k):
if prev_color != color:
best_previous = min(best_previous, dp[area - 1][prev_color])
dp[area][color] = costs[area][color] + best_previous
return min(dp[n - 1])
코드 해설
1. 빈 입력 처리
if not costs:
return 0
칠할 구역이 없다면 비용도 없습니다.
2. 구역 수와 색 개수 구하기
n = len(costs)
k = len(costs[0])
n은 구역의 개수이고, k는 색의 개수입니다.
3. DP 배열 만들기
dp = [[0] * k for _ in range(n)]
dp[i][j]는 i번째 구역을 j번째 색으로 칠했을 때의 최소 누적 비용입니다.
4. 첫 번째 구역 초기화
for color in range(k):
dp[0][color] = costs[0][color]
첫 번째 구역은 이전 구역이 없으므로, 그 색을 칠하는 비용이 그대로 최소 비용입니다.
5. 현재 색과 다른 이전 색만 확인
for prev_color in range(k):
if prev_color != color:
best_previous = min(best_previous, dp[area - 1][prev_color])
현재 색과 이전 색이 같으면 안 됩니다.
그래서 prev_color != color 조건을 둡니다.
6. 현재까지의 최소 비용 저장
dp[area][color] = costs[area][color] + best_previous
현재 색을 칠하는 비용에 이전 구역까지의 가능한 최소 비용을 더합니다.
예제로 따라가기
입력은 다음과 같습니다.
costs = [
[7, 3, 8],
[6, 5, 2],
[4, 9, 1]
]
첫 번째 구역의 DP는 그대로 비용이 됩니다.
dp[0] = [7, 3, 8]
두 번째 구역을 계산합니다.
- 색 0 선택:
6 + min(3, 8) = 9 - 색 1 선택:
5 + min(7, 8) = 12 - 색 2 선택:
2 + min(7, 3) = 5
dp[1] = [9, 12, 5]
세 번째 구역을 계산합니다.
- 색 0 선택:
4 + min(12, 5) = 9 - 색 1 선택:
9 + min(9, 5) = 14 - 색 2 선택:
1 + min(9, 12) = 10
dp[2] = [9, 14, 10]
마지막 행에서 가장 작은 값이 정답입니다.
min([9, 14, 10]) = 9
따라서 최소 비용은 9입니다.
복잡도
위 풀이는 세 겹의 반복문이 있습니다.
- 구역 수
N - 현재 색
K - 이전 색
K
따라서 시간 복잡도는 다음과 같습니다.
O(N × K²)
공간 복잡도는 DP 배열을 사용하므로 다음과 같습니다.
O(N × K)
더 생각해볼 점
색의 개수 K가 작다면 O(N × K²)도 괜찮을 수 있습니다.
하지만 K가 매우 크다면 매번 이전 색 전체를 확인하는 부분이 부담될 수 있습니다.
이때는 이전 행에서 가장 작은 값과 두 번째로 작은 값을 미리 기억하면 더 빠르게 풀 수 있습니다.
현재 색이 이전 행의 최소값과 같은 색이면 두 번째 최소값을 사용하고, 다른 색이면 최소값을 사용하면 됩니다.
이렇게 하면 시간 복잡도를 다음처럼 줄일 수 있습니다.
O(N × K)
최적화 아이디어
각 구역을 계산할 때 이전 행에서 필요한 정보는 사실 두 가지입니다.
이전 행의 최소 비용
이전 행의 두 번째 최소 비용
왜 두 개가 필요할까요?
현재 색과 이전 최소 비용의 색이 다르면 최소 비용을 쓰면 됩니다.
하지만 현재 색과 이전 최소 비용의 색이 같으면, 같은 색을 연속으로 쓸 수 없으므로 두 번째 최소 비용을 써야 합니다.
최적화 코드
def min_paint_cost_optimized(costs):
if not costs:
return 0
n = len(costs)
k = len(costs[0])
prev = costs[0][:]
for area in range(1, n):
min1 = float("inf")
min2 = float("inf")
min1_color = -1
for color in range(k):
if prev[color] < min1:
min2 = min1
min1 = prev[color]
min1_color = color
elif prev[color] < min2:
min2 = prev[color]
current = [0] * k
for color in range(k):
if color == min1_color:
current[color] = costs[area][color] + min2
else:
current[color] = costs[area][color] + min1
prev = current
return min(prev)
최적화 코드 해설
1. 이전 행의 최소값과 두 번째 최소값 찾기
min1 = float("inf")
min2 = float("inf")
min1_color = -1
min1은 이전 구역까지의 최소 비용입니다.
min2는 두 번째 최소 비용입니다.
min1_color는 최소 비용을 만든 색 번호입니다.
2. 현재 색이 이전 최소 색과 같을 때
if color == min1_color:
current[color] = costs[area][color] + min2
현재 색이 이전 최소 비용의 색과 같다면, 같은 색을 연속으로 사용할 수 없습니다.
그래서 두 번째 최소 비용을 사용합니다.
3. 현재 색이 이전 최소 색과 다를 때
else:
current[color] = costs[area][color] + min1
현재 색이 이전 최소 비용의 색과 다르면, 그대로 최소 비용을 사용할 수 있습니다.
최적화 버전 복잡도
최적화 버전은 각 구역마다 색을 두 번만 훑습니다.
- 최소값과 두 번째 최소값 찾기
- 현재 행 계산하기
따라서 시간 복잡도는 다음과 같습니다.
O(N × K)
공간 복잡도는 이전 행과 현재 행만 사용하므로 다음과 같습니다.
O(K)
헷갈리기 쉬운 부분
1. 현재 구역에서 가장 싼 색만 고르면 안 됨
현재 구역만 보면 가장 싼 색이 좋아 보일 수 있습니다.
하지만 바로 이전 구역과 색이 같으면 선택할 수 없습니다.
그래서 이전 구역의 선택까지 고려해야 합니다.
2. dp[i][j]의 의미를 정확히 잡아야 함
dp[i][j]는 단순히 i번째 구역의 j색 비용이 아닙니다.
정확히는 다음 뜻입니다.
i번째 구역을 j색으로 칠했을 때의 최소 누적 비용
이 의미를 잡지 못하면 점화식이 헷갈립니다.
3. 마지막 정답은 마지막 행의 최솟값
모든 구역을 다 칠한 뒤, 마지막 구역이 어떤 색인지 꼭 정해져 있지는 않습니다.
따라서 마지막 행에서 가장 작은 값을 고르면 됩니다.
return min(dp[n - 1])
정리
이번 글에서는 인접한 구역에 같은 색을 사용할 수 없을 때, 전체 비용을 최소로 만드는 방법을 정리했습니다.
핵심은 DP 상태를 이렇게 정의하는 것입니다.
dp[i][j] = i번째 구역을 j색으로 칠했을 때의 최소 누적 비용
그리고 현재 색과 이전 색이 같으면 안 되므로, 이전 구역에서 다른 색을 선택한 경우 중 최솟값을 더합니다.
정리하면:
현재 비용 = 현재 색 비용 + 이전 구역에서 다른 색을 선택한 최소 비용
기본 풀이는 O(N × K²)이고,
이전 행의 최소값과 두 번째 최소값을 활용하면 O(N × K)까지 줄일 수 있습니다.
이 문제는 인접 조건이 있는 DP 문제를 연습하기 좋은 예제입니다.