[백준] 1149 RGB거리 (Python 파이썬)

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

1149번: RGB거리

문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

---

풀이 과정

이 문제는 DP(다이나믹 프로그래밍)을 이용해 앞에서 부터 최소값을 저장해 나가며

모든 집을 칠했을 때의 최소값을 구하는 문제이다.

 

먼저 Nx3 모양의 2차원 DP배열을 만들어

R, G, B 페인트를 칠했을 때의 최솟값들을 저장해주자.

예를 들어, DP[N][0]은 현재 N번집에 R 페인트를 칠했을 때의 최솟값을 저장하게 된다.

 

첫 집은 R, G, B 모두를 선택할 수 있으므로

DP[0][0]에는 첫 번째 집의 R비용을,

DP[0][1]에는 첫 번째 집의 G비용을,

DP[0][2]에는 첫 번째 집의 B비용을 각각 저장하자.

 

두 번째 집부터, 바로 전집과는 다른 색을 칠해야 하므로

두번째 집에 R을 선택했다면 이전집에서는 G,B 를 칠한 것 중 최솟값을 선택하여 더하면 된다.

 

이러한 방식으로 값을 누적해나가 마지막 집의 DP값을 구하면 답을 구할 수 있다.

n = int(input())

cost = []
minCost = -int(1e9)
dp = [[0]*3 for _ in range(n)]
for i in range(n):
    cost.append(list(map(int, input().split())))

dp[0][0], dp[0][1], dp[0][2] = cost[0][0], cost[0][1], cost[0][2]

for i in range(1, n):
    dp[i][0] = min(dp[i-1][1] + cost[i][0], dp[i-1][2] + cost[i][0])
    dp[i][1] = min(dp[i-1][0] + cost[i][1], dp[i-1][2] + cost[i][1])
    dp[i][2] = min(dp[i-1][0] + cost[i][2], dp[i-1][1] + cost[i][2])

print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !