[python 백준] 1149 번 : RGB

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

문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1 복사

3
26 40 83
49 60 57
13 89 99

예제 출력 1 복사

96

예제 입력 2 복사

3
1 100 100
100 1 100
100 100 1

예제 출력 2 복사

3

예제 입력 3 복사

3
1 100 100
100 100 100
1 100 100

예제 출력 3 복사

102

예제 입력 4 복사

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

예제 출력 4 복사

208

예제 입력 5 복사

8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

예제 출력 5 복사

253

 

해당 문제는 각 집을 칠할 때마다 그 전 집이 어떤 색으로 칠해졌는지에 따라 가능한 선택지가 달라집니다. 예를 들어, 2번 집이 빨강으로 칠해졌다면 1번 집은 초록이나 파랑으로 칠해야 합니다. 이런 식으로 각 집마다 그 전 집의 색깔에 의존하게 됩니다. 그리하여 동적 계획법으로 문제를 풀어야 합니다.

모든 경우의 수를 일일이 다 계산하는 것은 비효율적입니다. 각 집의 색에 대한 비용을 저장해 두고, 이미 계산된 결과를 재사용할 수 있다면 훨씬 빠르게 계산할 수 있습니다. 동적 계획법은 바로 이러한 중복 계산을 피하고 문제를 최적화하는 방법입니다.

 

 

• dp[i][0]: i번째 집을 빨강으로 칠할 때의 최소 비용
• dp[i][1]: i번째 집을 초록으로 칠할 때의 최소 비용
• dp[i][2]: i번째 집을 파랑으로 칠할 때의 최소 비용
  
  이전 집의 색깔을 고려하면서 현재 집의 최소 비용을 계산할 수 있습니다.

 

• i번째 집을 빨강으로 칠할 경우:
  • dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]
  • 즉, i-1번째 집이 초록이거나 파랑으로 칠해졌을 때의 최소 비용 중 더 작은 값을 선택하고, 현재 집을 빨강으로 칠하는 비용을 더합니다.
• i번째 집을 초록으로 칠할 경우:
  • dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]
  • 즉, i-1번째 집이 빨강이거나 파랑으로 칠해졌을 때의 최소 비용 중 더 작은 값을 선택하고, 현재 집을 초록으로 칠하는 비용을 더합니다.
• i번째 집을 파랑으로 칠할 경우:
  • dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]
  • 즉, i-1번째 집이 빨강이거나 초록으로 칠해졌을 때의 최소 비용 중 더 작은 값을 선택하고, 현재 집을 파랑으로 칠하는 비용을 더합니다.

마지막 집의 최소값

마지막 집에서 빨강, 초록, 파랑으로 칠하는 세 가지 경우 중에서 가장 작은 값을 선택하면 됩니다:

• result = min(dp[N-1][0], dp[N-1][1], dp[N-1][2])

초기 상태:

 

코드 복사

집 1: 빨강(R): 26 초록(G): 40 파랑(B): 83

1번 집은 빨강, 초록, 파랑으로 각각 칠하는 비용을 바로 DP 테이블에 넣습니다:

 

dp[0][0] = 26 (빨강) dp[0][1] = 40 (초록) dp[0][2] = 83 (파랑)

2번 집은 이전 집의 색에 의존하여 최소 비용을 구합니다:

 

집 2: 빨강: dp[1][0] = min(dp[0][1], dp[0][2]) + 49 = min(40, 83) + 49 = 89 초록: dp[1][1] = min(dp[0][0], dp[0][2]) + 60 = min(26, 83) + 60 = 86 파랑: dp[1][2] = min(dp[0][0], dp[0][1]) + 57 = min(26, 40) + 57 = 83

3번 집도 마찬가지로 계산:

 

집 3: 빨강: dp[2][0] = min(dp[1][1], dp[1][2]) + 13 = min(86, 83) + 13 = 96 초록: dp[2][1] = min(dp[1][0], dp[1][2]) + 89 = min(89, 83) + 89 = 172 파랑: dp[2][2] = min(dp[1][0], dp[1][1]) + 99 = min(89, 86) + 99 = 185

결과적으로 마지막 집에서 최소값을 선택:

scss

코드 복사

최소 비용 = min(96, 172, 185) = 96

따라서 정답은 96입니다.

 

 

n = int(input())

house = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*3 for _ in range(n)]

dp[0][0] = house[0][0]
dp[0][1] = house[0][1]
dp[0][2] = house[0][2]

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

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