[Python Algorithm] RGB거리 BOJ #1149

문제

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

1149번: RGB거리

 

내 문제 풀이

n = int(input())

r, g, b = map(int, input().split())
red = [r]
green = [g]
blue = [b]

for i in range(1, n):
    r, g, b = map(int, input().split())
    red.append(r + min(green[i-1], blue[i-1]))
    green.append(g + min(red[i-1], blue[i-1]))
    blue.append(b + min(red[i-1], green[i-1]))

print(min(red[-1], blue[-1], green[-1]))

👉DP 문제로, 연속되는 집 마다 어떤색으로 칠한다면?을 가정하여 푸는 것이 포인트!

• 집을 빨, 초, 파 셋 중 하나로 칠하는데, 같은 색이 연속될 수 없다.
  이 얘기는 즉, 빨간색으로 칠했다면 그 이전 집은 초록이나 파란색으로 칠했다는 의미이며,
  최소 비용을 구하기 위해서는 이전 집의 초록과 파랑 중 더 저렴한 색을 선택하는 것이 이득이된다는 뜻!
• 최소 비용이 될 수 있는 경우의 수는 총 세 가지로 볼 수 있다. 
  => '현재' 순서의 집을 빨간색으로 칠하는 경우, 혹은 파란색, 혹은 초록색으로 칠하는 경우.
• 따라서 우리는 총 세 가지 경우의 수를 구하기 위한 세 개의 리스트를 만들고, 
  리스트마다 최소가 될 수 있는 선택을 하여 비용을 누적한다.
  그리고 세 리스트의 마지막 요소 중 가장 작은 값을 골라서 결과로 출력한다.

(이전에 swift로 풀었던 글에 더 자세한 설명 있음. https://seolhee2750.tistory.com/138)

 

💡 피드백

• 최소 비용을 구할 수 있는 최소한의 경우의 수를 구하는 것이 관건인데, 대표적인 dp 알고리즘 유형인 것 같고,
  이전에 swift를 이용하여 풀었던 경험이 있어서 금방 풀 수 있었음.