백준 1149번 RGB거리 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 1149 RGB거리

1149 RGB거리

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

1149번: RGB거리

 

이전의 집과 색이 같지 않고, 다음 집의 색이 같지 않아야 한다. 이 조건을 만족하며 비용의 최솟값 또한 고려해야 한다.

 

알고리즘 분류

• 다이내믹 프로그래밍

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
RGB = [list(map(int, input().split())) for i in range(n)]

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

---

풀이

n개의 집을 칠하는데 각 집마다 빨초파 페인트의 가격이 다르기 때문에 가격을 리스트로 묶어 n개를 입력받는다.

첫 번째 집의 색은 고려하지 않아도 괜찮기 때문에 두 번째 집부터 계산한다.

현재의 집이 앞의 집과 다음 집의 색과 다르기 위해서는 이전 집의 색을 고려한 계산을 해주면 끝까지 겹치는 색은 나올 수 없다.

RGB[i][0] = 빨강일 때를 의미하고 이 경우에는 이전 집이 초록이거나 파랑일 때 더 싼 페인트를 사용한 집을 고르게 된다.

이러한 방식으로 빨, 초, 파일 모든 경우의 비용을 이전 dp와 더해 진행한다. 이후에는 마지막 요소의 최솟값을 출력하면 된다.

---

풀이 결과

1149 풀이 결과