[백준] RGB거리

출처:: www.acmicpc.net/problem/1149

분류:: dp

 

1. 문제 이해 및 해결과정

- 각 열에서 한 개씩 선택해서  단, 색상조건 고려해야함  - i가 빨강으로 칠해질때, i-1에는 초록이나 파랑 칠해져 있어야한다.  - i가 파랑으로 칠해질때, i-1에는 초록이나 빨강 칠해져 있어야한다. - i가 초록으로 칠해질때, i-1에는 빨강이나 파랑 칠해져 있어야한다.    dp[i][j] : 집i번까지  j색으로 칠했을 때 최소비용      => dp[i][r] = min(dp[i-1][g], dp[i-1][b]) + cost[i][r] ,g,b도 이와 같다                               0  1   2   번 집 빨간색으로 칠해질 때, 26 40 83 초록색으로 칠해질 때, 49 60 57 파랑색으로 칠해질 때, 13 89 99 26 40 83  ex)dp[0][0] 0번집을 빨강으로 칠했을 때 비용 89  86 83    ex)dp[1][0] 1번까지 칠했는데, 1번집을 빨강색으로 칠할 경우 = 0번 집에서는 초록, 파랑 으로 칠해야함  96  172  185  ex) dp[2][1]  2번까지 칠했는데, 2번집을 초록으로 칠했을 경우 = 1번까지 최소 비용중 골라야함

 

2. 풀이방법

  1. [python]

#RGB거리
#https://www.acmicpc.net/problem/1149
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n=int(input())
cost=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*n for _ in range(n)]

for i in range(3): #dp 초기화 
    dp[0][i]=cost[0][i]
for i in range(1,n):
    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]
    # print(dp)
print(min(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

 

3. 오답원인

 

4. 알게된 점