[Python] 1149번 RGB거리, 문제 완벽 분석!! 그림 설명

✏️ 문제

 

문제 파악

조건이 3가지가 있는데 축약해보면 n번 집은 n-1의 집과 색만 같지 않으면 된다. n-1의 집과 n+1의 집의 색은 같아도 상관없다.

이전 집의 색만 겹치지 않는 걸 조건으로 문제를 풀이하면 다음과 같다.

ary 배열은 하나의 집에 대한 색 비용을 각각 담은 배열이고 dp 배열은 하나의 집에 대한 최소 색 비용의 총 합을 담은 배열이다.

 

다음 집의 색은 현재 선택할 색의 비용과 다음 선택할 색의 비용의 합이 최소로 되는 것으로 선택해야 한다.

이게 무슨 말이냐면 dp 배열의 2행 색을 선택할 때 최소 비용을 고르려고 한다면 

• 1번째 집이 R을 선택했을 시 경우의 수는 2가지
  • R-G : 26 + 60 = 86 
  • R-B : 26 + 57 = 83
  • G와 B 중에 최소인 B를 선택할 것이므로 R-B값을 2번째 행 R열에 대입
• 1번째 집이 G를 선택했을 시 경우의 수는 2가지
  • G-R : 40 + 49 = 89
  • G-B : 40 + 57 = 97
  • R와 B 중에 최소인 R를 선택할 것이므로 G-R 값을 2번째 행 G열에 대입
• 1번째 집이 B를 선택했을 시 경우의 수는 2가지
  • B-R : 83 + 49 = 132
  • B-G : 83 + 60 = 143
  • R와 G 중에 최소인 R를 선택할 것이므로 B-R 값을 2번째 행 B열에 대입

이렇게 dp 의 2번째 행을 다 채웠다면 2번째 행들의 값 중 제일 최소를 선택하는 것이 이때까지 제일 최소 비용을 사용해 집 색을 칠해왔다는 것이 된다.

 

 

알고리즘

• 다이나믹 프로그래밍 

 

 

코드

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

for i in range(1,n):
  dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0] # 현재 행을 R 선택 
  dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1] # 현재 행을 G 선택
  dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2] # 현재 행을 B 선택

print(min(dp[n-1])) # 배열은 0부터 시작하므로