[BOJ 1149번] RGB 거리
1. 문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
2. 문제 풀이
i번째 집을 빨간색, 초록색, 파란색으로 색칠했을 때를 생각해보면 된다.
각 행은 i번째 집을 빨간색, 초록색, 파란색으로 색칠했을 때의 비용이므로
만약 집을 빨간색으로 색칠한다면, 그 전 집은 파란색과 초록색 중 더 적은 비용인 색깔로 칠해야 한다(색이 겹치면 안되므로)
이렇게 for문을 반복하면서 각 집을 빨간색, 초록색, 파란색으로 칠했을 때, 어떠한 색깔로 칠하는 것이 가장 비용이 적게 드는지를 확인한다.
1) house 리스트의 첫번째 행을 첫번째 집을 각각 빨간색, 초록색, 파란색으로 칠했을 때로 초기화한다.
2) 반복문을 통해 N번째 집을 각각 빨간색, 초록색, 파란색으로 칠했을 때의 최소 비용을 계산하여 테이블에 저장한다.
3) 테이블의 마지막 행(N번 집까지 색칠한 후의 최소 비용이 저장된 테이블)을 확인하여 그 중 가장 적은 비용을 찾아 출력한다.
import sys
N = int(sys.stdin.readline())
house =[[0 for _ in range(3)] for _ in range(N)]
cost = []
for i in range(N):
cost.append(list(map(int, sys.stdin.readline().split())))
house[0][0], house[0][1], house[0][2] = cost[0][0], cost[0][1], cost[0][2]
for i in range(1, N):
house[i][0] = min(house[i-1][1], house[i-1][2]) + cost[i][0]
house[i][1] = min(house[i-1][0], house[i-1][2]) + cost[i][1]
house[i][2] = min(house[i-1][0], house[i-1][1]) + cost[i][2]
print(min(house[-1]))
# 초기 상태(첫번째 집)
dp = [
[26, 40, 83]
]
# 두번째 집
#두번째 집을 빨간색으로 칠했을 때, 앞의 집이 초록색과 파란색인 경우를 확인
#그 중 최소값을 두번째 집을 빨간색으로 칠했을 때의 최소값과 더하기
dp[1][0] = min(dp[0][1], dp[0][2]) + costs[1][0]
= min(40, 83) + 49
= 89
#두번쨰 집을 초록색으로 칠했을 때, 앞의 집이 빨간색이거나 파란색인 경우를 확인
#그 중 최소값을 두 번째집을 초록색으로 칠했을 때의 최소값과 더하기
dp[1][1] = min(dp[0][0], dp[0][2]) + costs[1][1]
= min(26, 83) + 60
= 86
#두번째 집을 파란색으로 칠했을 때, 앞의 집이 빨간색이거나 초록색인 경우를 확인
#그 중 최소값을 두 번쨰집을 파란색으로 칠했을 때의 최소값과 더하기
dp[1][2] = min(dp[0][0], dp[0][1]) + costs[1][2]
= min(26, 40) + 57
= 83
dp = [ [26, 40, 83],
[89, 86, 83]
]
문제 이해하는게 더 어렵다요..