목차
https://www.acmicpc.net/problem/1149
동적계획법 즉 DP를 활용하여 문제를 해결할 수 있다.
그림을 통하여 문제를 조금 더 간편하게 이해해보자.
- 문제 이해
- N개의 집이 있고, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다.
- 인접한 집들은 서로 다른 색으로 칠해져야 한다.
- 각 집을 각 색으로 칠하는 비용이 주어진다.
- 목표는 모든 규칙을 만족하면서 전체 비용을 최소화하는 것.
- 해결 접근 방식 (동적 프로그래밍)
- 그림에서 보이듯이, 각 단계(집)마다 3가지 선택(R, G, B)이 존재.
- 각 단계에서의 최소 비용은 이전 단계의 결과에 의존.
- 따라서 이를 해결하려면 전에 단계에서 가져올 수 있는 숫자중 최소를 구한 후, 현재 위치와 더하면 된다!
- 이를 계속 한 행마다 반복해준다면 마지막 행 중 최소 값을 구하면 답이 나온다!
- DP 테이블 구성
- DP[i][j]: i번째 집을 j색으로 칠했을 때의 최소 비용 (j = 0: 그림에서 검정색, j = 1: 그림에서 파랑색, j = 2: 그림에서 빨간색)
- 점화식
- DP[i][0] = min(DP[i-1][1], DP[i-1][2]) + cost[i][0] (오른쪽 대각선 두개 중 최소)
- DP[i][1] = min(DP[i-1][0], DP[i-1][2]) + cost[i][1] (왼쪽 대각선 , 오른쪽 대각선 중 최소)
- DP[i][2] = min(DP[i-1][0], DP[i-1][1]) + cost[i][2] (왼쪽 대각선 두개 중 최소)
- 구현 단계
- a) 입력 받기: N과 각 집의 색칠 비용
- b) DP 테이블 초기화: 첫 번째 집의 비용으로 초기화 c) 두 번째 집부터 N번째 집까지 반복:
- 각 색상에 대해 이전 집의 다른 두 색상 중 최소 비용을 선택하고 현재 비용을 더함
- d) 마지막 행(N번째 집)에서 최소값을 선택하여 출력
- 시간 복잡도는 O(N)이다.
구체적인 코드는 아래와 같다.
n = int(input())
cost = []
for i in range(n):
cost.append(list(map(int,input().split())))
for i in range(1, n):
cost[i][0] = min(cost[i-1][1], cost[i-1][2]) + cost[i][0]
cost[i][1] = min(cost[i-1][0], cost[i-1][2]) + cost[i][1]
cost[i][2] = min(cost[i-1][0], cost[i-1][1]) + cost[i][2]
print(min(cost[-1]))
'백준' 카테고리의 다른 글
백준-11727번 2xn 타일링 2 (0) | 2024.08.16 |
---|---|
백준-9095번 1,2,3 더하기 (0) | 2024.08.16 |