백준-1149번 RGB거리

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]))