[백준] 1149. rgb 거리 python

🐳 링크

백준 rgb거리

🐕 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

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

🐾 풀이 방법

26 40 83 # 1번집, 빨, 초, 파
49 60 57 # 2번집, 빨, 초, 파
13 89 99 # 3번집, 빨, 초, 파

2번집을 빨강색으로 칠하게 된다면 1번집은 초록, 파랑만이 가능하다. 이 논리를 바탕으로 2번집을 빨강색으로 칠할 때에는 1번 집을 초록색으로 칠한 경우와 파란색으로 칠한 경우의 값 중 최솟값에 2번집을 빨강색으로 칠하는 비용을 합한다.
house[1][0] = min(house[0][1], house[0][2]) + house[1][0]

3번집을 빨강색으로 칠하게 되는 경우도 마찬가지이다. 3번 집을 빨강색으로 칠하게 된다면 2번 집은 초록, 파랑만이 가능하다. 이 때, 2번 집의 경우에는 위 경우를 통해 해당 색에 따라 최소 비용이 들도록 1번 집을 색칠한 값에 2번집의 경우가 더해져있으므로, 3번 집과 색만 겹치지 않도록 하여 다시 더해주면 된다.

약간 횡설수설한데,, 요약해보자면

• 2번집을 빨강으로 색칠하는 경우
  -> 1번 집은 파랑, 초록만 가능하다.
  -> 따라서 파랑, 초록 중 최소비용을 갖는 색으로 결정한다.
  -> 이후 2번집을 빨강으로 칠하는 비용과 합해준다.
  -> 그 칸은 1번 집과 2번 집을 색칠하는 비용이 모두 합해지게 된다.
• 3번집을 빨강으로 색칠하는 경우
  -> 2번 집은 파랑, 초록만 가능하다.
  -> 따라서 2번집의 파랑, 초록 중 최소비용을 갖는 색으로 결정한다.
  -> 2번 집에는 1번 집 비용도 합해져있으므로, 2번집 비용에 3번집의 비용을 합하면 모든 비용이 된다.

소스코드

import sys
sys.stdin = open("input.txt","rt")

n = int(sys.stdin.readline().strip())
house = list()

for _ in range(n):
    house.append(list(map(int,sys.stdin.readline().split())))
for i in range(1,n):
    house[i][0] = min(house[i-1][1], house[i-1][2]) + house[i][0]
    house[i][1] = min(house[i-1][0], house[i-1][2]) + house[i][1]
    house[i][2] = min(house[i-1][0], house[i-1][1]) + house[i][2]
print(min(house[n-1]))