📚문제: #1149 RGB거리(Silver 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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력 1
(입력)
3
26 40 83
49 60 57
13 89 99
(출력)
96예제 입력 2
(입력)
3
1 100 100
100 1 100
100 100 1
(출력)
3예제 입력 3
(입력)
3
1 100 100
100 100 100
1 100 100
(출력)
102예제 입력 4
(입력)
6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91
(출력)
208예제 입력 5
(입력)
8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19
(출력)
253아이디어 및 구현
- DP 계산을 수행한다. DP[i][j]에 DP[i-1] 중에서 j열과 겹치지 않는 두 열의 값 중 더 작은 값을 더해준다.
# j가 0번째 열이면, i-1행의 1,2번째 열의 값을 비교하여 작은 값을 더한다.
if j == 0:
dp[i][j] = min(dp[i][j]+dp[i-1][j+1], dp[i][j]+dp[i-1][j+2])
# j가 1번째 열이면, i-1행의 0,2번째 열의 값을 비교하여 작은 값을 더한다.
elif j == 1:
dp[i][j] = min(dp[i][j]+dp[i-1][j-1], dp[i][j]+dp[i-1][j+1])
# j가 2번째 열이면, i-1행의 0,1번째 열의 값을 비교하여 작은 값을 더한다.
else: # j == 2
dp[i][j] = min(dp[i][j]+dp[i-1][j-2], dp[i][j]+dp[i-1][j-1])전체 코드
import sys
# 집의 수 N이 주어집니다.
N = int(sys.stdin.readline().rstrip())
# N개의 줄에 각 집에 대해 R, G, B로 칠하는 비용이 주어집니다.
dp = []
for _ in range(N):
dp.append(list(map(int, sys.stdin.readline().split())))
# (index : 1 ~ N-1)
for i in range(1, N):
for j in range(3):
if j == 0:
dp[i][j] = min(dp[i][j]+dp[i-1][j+1], dp[i][j]+dp[i-1][j+2])
elif j == 1:
dp[i][j] = min(dp[i][j]+dp[i-1][j-1], dp[i][j]+dp[i-1][j+1])
else: # j == 2
dp[i][j] = min(dp[i][j]+dp[i-1][j-2], dp[i][j]+dp[i-1][j-1])
# DP 테이블의 마지막 행의 값 중 최솟값을 출력
print(min(dp[N-1]))