[백준 BOJ] 1149 RGB거리 (python)

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

1149번: RGB거리

 

 🚨 작성 코드

N = int(input())

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

for i in range(1, N):
    arr[i][0] += min(arr[i-1][1], arr[i-1][2])
    arr[i][1] += min(arr[i-1][2], arr[i-1][0])
    arr[i][2] += min(arr[i-1][0], arr[i-1][1])
result = min(arr[N-1][0], arr[N-1][1], arr[N-1][2])

print(result)

 

⭕ 해설

1.  arr[i]의 0, 1, 2의 요소에는 빨강, 초록, 파랑 중 하나의 색으로 칠할 때의 가격이 적혀있습니다.
2.  만약 2번째 집을 칠할 때, 3가지의 경우로 생각해 볼 수 있습니다.
   • 빨강 => 1번 집은 초록, 파랑 중 저렴한 가격을 선택한다.
   • 초록 => 1번 집은 파랑, 빨강 중 저렴한 가격을 선택한다.
   • 파랑 => 1번 집은 빨강, 초록 중 저렴한 가격을 선택한다,
3. 그 다음 3번 집을 칠할 때에는, 2번집을 칠할때까지 최소 비용을 고려하여야 합니다.
4. 따라서 2번집에 각각의 색을 칠할 때의 최소비용을 골라두고, 3번 집을 칠할 때 이것을 더해줍니다.
   •  빨강 => 2번 집을 초록, 파랑으로 칠 한 것 중 저렴한 가격
   •  초록 => 2번 집을 파랑, 빨강으로 칠 한 것 중 저렴한 가격
   •  파랑 => 2번 집을 빨강, 초록으로 칠 한 것 중 저렴한 가격
5.  앞에서 이미 2번 집을 칠할 때, 각각의 색마다 가장 저렴한 방법을 고려해왔으므로, 3번 집을 칠하는 3가지 방법들은 각각 가능한 두 가지 방법 중에서 선택하면 됩니다.
6.  n번 집을 빨강, 초록, 파랑으로 칠할 때까지 최소 비용을 저장해놓습니다.
7.  다 구한 다음 arr[n-1]의 세 가지 원소 중 가장 작은 값을 출력합니다.