[백준/Python] 1149번: RGB거리

문제

https://www.acmicpc.net/problem/1149

1149번: RGB거리

---

문제 요약

RGB거리에 집이 N개 있다. (거리는 선분으로 나타낼 수 있다.)

 

모든 집들을 빨강, 초록, 파랑 중 하나의 색으로 칠해야한다.

 

각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

규칙 1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다.

 

규칙 2. N번 집은 N-1번 집의 색과 같지 않아야 한다.

 

규칙 3. i번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. (2 ≤ i ≤ N-1)

---

코드

import copy

N = int(input()) # 집의 수

infor = []
# infor[i]는 i번 집을 색칠할 때 드는 비용 [빨강, 초록 파랑]

for _ in range(N):
    infor.append(list(map(int, input().split())))

dp = [[10000000] * N for _ in range(N)]
# dp[i]는 i번 집까지 색칠할 때, 최소 비용 저장 [빨강, 초록, 파랑]

dp[0] = infor[0].copy()

for i in range(1, N): # 1번 집부터 N-1번 집까지
    # 빨강, 초록, 파랑 순으로 dp[i] 갱신
    dp[i][0] = min(dp[i-1][1] + infor[i][0], dp[i-1][2] + infor[i][0])
    dp[i][1] = min(dp[i-1][0] + infor[i][1], dp[i-1][2] + infor[i][1])
    dp[i][2] = min(dp[i-1][0] + infor[i][2], dp[i-1][1] + infor[i][2])
    
#print(dp)
print(min(dp[N-1]))

---

코드 설명

1. 각 집들의 색칠할 때 비용을 2차원 배열에 저장한다. (0번 집부터 N-1번 집까지 존재)

 

+ 한 행에 빨강, 초록, 파랑 비용을 모두 저장해야 하기 때문에 2차원 배열을 사용한다.

 

2. i번 집까지 색칠할 때 발생하는 최소 비용을 저장할 2차원 메모이제이션 테이블 dp[i]를 생성한다.

 

+ 초기 값: 최악의 경우 N의 최대 개수 × 최대 비용 = 100,000,000

 

+ 0번 집은 입력 받은 비용 그대로 저장한다.

 

3. 1번 집부터 N - 1번 집까지 이전 집의 dp값에 자신의 비용을 더한 값을 비교하여 갱신한다.

 

ex) i번 집을 빨강으로 색칠할 때 최소 비용은 i-1번 집을 파랑으로 색칠할 때 최소 비용 + i번 집을 빨강으로 색칠할 때 비용과 i-1번 집을 초록으로 색칠할 때 최소 비용 + i번 집을 빨강으로 색칠할 때 비용 중 더 작은 비용이다.

 

4. N-1번 집까지 색칠할 때 발생하는 비용 중 최소 비용을 출력한다.