[백준/파이썬] 1149번 RGB거리 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1149번 RGB거리
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

각 집을 빨강/초록/파랑 중 하나로 칠할 때, 인접한 집의 색이 같지 않도록 하면서 전체 비용의 최솟값을 구하는 문제입니다.

코드

street = []
    
n = int(input())
for i in range(n):
    street.append(tuple(map(int, input().split())))

values = [(street[0][0], street[0][1], street[0][2])]
for i in range(1, n):
    x = min(values[i-1][1],values[i-1][2]) + street[i][0]
    y = min(values[i-1][2],values[i-1][0]) + street[i][1]
    z = min(values[i-1][0],values[i-1][1]) + street[i][2]
    values.append((x, y, z))

print(min(values[n-1]))

설명

values[i][color]를 i번째 집까지 칠했을 때 해당 색으로 끝나는 최소 비용으로 둡니다.

현재 집을 빨강으로 칠하면 이전 집은 초록/파랑 중 최소만 가능하므로:

• R = min(prevG, prevB) + costR
• G = min(prevB, prevR) + costG
• B = min(prevR, prevG) + costB

를 반복 계산하고 마지막 집의 최소값을 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---