https://www.acmicpc.net/problem/1149
1149번: RGB거리첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나www.acmicpc.net
dp 문제는 일단 식만 세우면 해결되는듯하다. 식세우기가어렵지만..
먼져 cost로 각 집을 칠하는 값을 구해놓는다.
그후 dp를 돌릴 배열을 선언한다.
dp[1]은 아무 제약이 없으므로, cost[1]과 같다.
dp[i][j]는 i번째의 집을 j색(0,1,2)으로 칠할 때의 최소비용을 뜻한다.
우리는 두 집을 같은 색으로 칠할 수 없으므로,
만일 마지막 집을 0으로 칠했다면, 막전 집은 1 또는 2여야만 한다.
j=0이라면
그러므로 dp[i-1][1], dp[i-1][2] 의 최솟값에 cost[i][0]을 더해준 것이 마지막을 0으로 칠했을 때의 최솟값이 된다.
우리가 구하는 것은 dp[i]의 최솟값이므로, min()을 통해 구한다.
DP
| Column 1 | Column 2 | Column 3 |
|---|---|---|
| 0 | 1 | 2 |
| cost[1][0] | cost[1][1] | cost[1][2] |
| min(dp[1][1]+cost[2][1],dp[1][2]+cost[2][1]) | min(dp[1][0]+cost[2][1],dp[1][2]+cost[2][1]) | min(dp[1][0]+cost[2][1],dp[1][1]+cost[2][1]) |
n=int(input())cost=[[-1,-1,-1]]dp=[[0]*3 for _ in range(n+1)]
##dp[i][j]=i번째의 집을 j색으로 칠할때의 최소비용for _ in range(n):
cost.append(list(map(int,input().split())))dp[1]=cost[1]
for i in range(2,n+1): for j in range(3): if j==0:
dp[i][j]=min(dp[i-1][1]+cost[i][j],dp[i-1][2]+cost[i][j])
elif j==1:
dp[i][j]=min(dp[i-1][0]+cost[i][j],dp[i-1][2]+cost[i][j])
elif j==2:
dp[i][j]=min(dp[i-1][0]+cost[i][j],dp[i-1][1]+cost[i][j])
print(min(dp[n]))