[실버 1] 백준 1149 - RGB거리 (파이썬)

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

풀이

집이 N개 있고, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나로 색칠해야 한다.

조건: 인접한 집은 같은 색을 칠할 수 없다.

즉, 각 집을 칠하는 비용이 주어졌을 때, 모든 집을 칠하는 최소 비용을 구하는 문제이다.

R[0] = C[0][0]  # 첫 번째 집을 빨강으로 칠했을 때 비용
G[0] = C[0][1]  # 첫 번째 집을 초록으로 칠했을 때 비용
B[0] = C[0][2]  # 첫 번째 집을 파랑으로 칠했을 때 비용

두번째 집부터는 이전 집과 색이 달라야 하므로, 각 색에 대해 아래와 같이 계산한다.

R[i] = C[i][0] + min(G[i - 1], B[i - 1])
G[i] = C[i][1] + min(R[i - 1], B[i - 1])
B[i] = C[i][2] + min(R[i - 1], G[i - 1])

현재 집을 빨강으로 칠하려면, 이전 집은 초록이나 파랑이어야 하므로, 그 둘 중 최소 비용을 더해준다.

나머지 색도 동일하게 처리한다.

print(min(R[N - 1], G[N - 1], B[N - 1]))

마지막 집을 어떤 색으로 칠하든 상관 없으니, 그 중 최소 비용을 출력한다.

코드

# 백준 1149 - RGB 거리
# 분류 : 다이나믹 프로그래밍

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

R = [0] * N
G = [0] * N
B = [0] * N

R[0] = C[0][0]
G[0] = C[0][1]
B[0] = C[0][2]

for i in range(1, N) :
    R[i] = C[i][0] + min(G[i - 1], B[i - 1])
    G[i] = C[i][1] + min(R[i - 1], B[i - 1])
    B[i] = C[i][2] + min(R[i - 1], G[i - 1])

print(min(R[N - 1], G[N - 1], B[N - 1]))