[백준] 1149번 : RGB거리 (Python)

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

 

 

이 문제는 N개의 집을 각각 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,

양옆의 집과 색이 같지 않으면서 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램이다.

 

n = int(input())  # 집의 수 입력 받기

# 각 집의 색상에 대한 비용 입력 받기
costs = []
for _ in range(n):
    costs.append(list(map(int, input().split())))

# 각 집에서 최소 비용을 누적으로 계산
for i in range(1, n):
    costs[i][0] += min(costs[i-1][1], costs[i-1][2])
    costs[i][1] += min(costs[i-1][0], costs[i-1][2])
    costs[i][2] += min(costs[i-1][0], costs[i-1][1])

# 마지막 집에서 선택한 색상 최소 비용
result = min(costs[-1])

print(result)

 

 

 

[문제풀이]

---

 

 

가장 최소의 경로만 선택하려고 하면 코드가 훨씬 복잡해진다.

구한 최소의 경로에다 집을 하나만 추가해도 또 이전에 구한 집의 최솟값이 최소값이 되지 않을수도 있기 때문이다.

 

그러니 R, G, B를 각각 선택했을때의 경로를 누적해서 더하여 가장 최소인 경로를 골랐다.

 

 

이렇게 누적한 경로 배열을 만들어 가장 최솟값을 선택하면 된다.