[S1] 백준 1149 - RGB거리 (Python3)

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

---

풀이 아이디어

동적 계획법(DP, Dynamic Programming) 알고리즘으로 해결한다.

각 집의 Red, Green, Blue 으로 색칠하는 비용이 주어졌을 때, 각 집을 칠할 때의 최소 비용을 계산한다. 이때 DP table을 이용해서 이전 집까지의 최소 비용을 가지고 현재 집을 칠할 때의 최소 비용을 구한다.

풀이👀

'현재 위치(i번째 집)에 대해서 전 후가 다른 색깔의 집이어야 한다.'는 조건이 걸려있다. 쉽게 풀어 설명하면 '연속해서 같은 색을 칠하지 말라'는 조건이다.

 

1. 첫 번째 집부터 마지막 집까지 반복하면서, 이전 까지의 최솟값으로 현재 집을 색칠할 때 최소 비용을 계산한다.

---

코드🐱‍👓

N = int(input())
RGB = [list(map(int, input().split())) for _ in range(N)]

INF = 1e5

dp = [[INF]*3 for _ in range(N)]

# 첫 번째 집을 칠하는 비용은 주어진 값과 같다.
dp[0] = RGB[0]

# Dynamic Programming을 이용하여 최소 비용을 계산한다.
for i in range(N-1):
    for j in range(3):
    	# 현재 집을 빨강, 초록, 파랑 중 하나로 칠했을 때의 최소 비용을 계산한다.
        # 이전 집의 색깔과 다른 색으로 칠하는 것이므로 (j+1)%3, (j+2)%3을 사용한다.
        dp[i+1][j] = min(dp[i+1][j], dp[i][(j+1)%3] + RGB[i+1][j], dp[i][(j+2)%3] + RGB[i+1][j])
        
print(min(dp[-1]))

---

유사한 유형의 문제

백준1932:정수 삼각형