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

# 1149 RGB거리

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

1149번: RGB거리

⭐ 코드

import sys
input = sys.stdin.readline

N = int(input())

house = []
for _ in range(N):
    R, G, B = map(int, input().split())
    house.append([R, G, B])

for i in range(1, len(house)):
    house[i][0] = house[i][0] + min(house[i-1][1], house[i-1][2])
    house[i][1] = house[i][1] + min(house[i-1][0], house[i-1][2])
    house[i][2] = house[i][2] + min(house[i-1][0], house[i-1][1])

print(min(house[-1][0], house[-1][1], house[-1][2]))

📝 풀이

RGB라는 3가지 색상이 있고, 1부터 N번 집이 순서대로 놓여져있다. 3가지 색상을 아래의 규칙을 만족하면서 색을 칠하는데에 드는 비용의 최솟값을 구하는 문제이다.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

조건을 자세히 살펴보면 인접한 집은 다른색이어야 한다는 뜻으로, 결국 인접한 집을 색칠하는 최소의 비용을 구하는 문제이다.

🔓 정답 코드 뜯어보기

N = int(input())

house = []
for _ in range(N):
    R, G, B = map(int, input().split())
    house.append([R, G, B])

입력 형식에 맞게 코드를 작성해준다. 집의 수 N만큼 반복문을 실행시켜서 house라는 리스트에 입력 값들을 append해준다.

# house = [[26, 40, 83], [49, 60, 57], [13, 89, 99]]
for i in range(1, len(house)):
    house[i][0] = house[i][0] + min(house[i-1][1], house[i-1][2])
    house[i][1] = house[i][1] + min(house[i-1][0], house[i-1][2])
    house[i][2] = house[i][2] + min(house[i-1][0], house[i-1][1])
# house = [[26, 40, 83], [89, 86, 83], [96, 172, 185]]
print(min(house[-1][0], house[-1][1], house[-1][2]))

위의 코드가 이번 문제의 핵심 코드이다. range의 시작을 1로 만들어 준 이유는, house리스트의 첫번째(인덱스0)의 값을 계속해서 더해주면서 다음 리스트에 넣어줄 것이기 때문이다. 즉, house(1)은 house(1)과 인접값 중 작은 값을 더한 최소비용을 더한 값이다. 최종적으로 house(2)의 값은 house(2)과 house(1)의 최소비용을 더한 값이므로 house(2)중 최소 값을 출력시켜주면 정답이 된다.