[백준 1149번] RGB 거리 in python

문제

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

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

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

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1

3
26 40 83
49 60 57
13 89 99

예제 출력 1

96

 

나머지 예제 확인은 밑의 주소에서

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

1149번: RGB거리

---

문제의 조건이 어렵게 설명되어 있지만 매우 간단하다. 색을 정할 때, 뒤에 정했던 색만 아니면 된다.

 

난 처음 i=0부터 비용을 하나씩 추가해서 가장 적은 비용을 나오게 만들었으나 답이 나오지 않았다.

사람들이 짠 코드를 봤을 때, 최단경로 알고리즘으로 짠 것 같았다.

i=1부터 자기 자신 색을 제외한 그 전 두가지 색 중 가장 비용이 작은 것을 자기 자신의 비용에 더 하는 방식으로 진행했다.

예를 들자

N=3(집이 3개)

r     g    b

1 100 100               i=0

100 1 100               i=1 

100 100 1               i=2

N=3	r	g	b
i=0	1	100	100
i=1	100	1	100
i=2	100	100	1

이런 경로가 있다.

두번째부터 시작이다!(i=1)

i=1일 때, r의 비용은 100이다. 그럼 그전에 집은 r을 제외한 g와 b가 왔어야 되는데, 그 중 비용이 작은 것을 선택한다.

그럼 i=1일 때, r까지 도달했던 비용은 200이 된다.

이처럼 g와 b도 수정해준다.

그러면 아래와 같은 표가 나온다.

i=1

200

2

101

 

다음으로 i=2로 넘어가자

위와 똑같이 i=2일 때 r의 비용은 100이다. 그럼 그전의 집은 g와 b가 와야 하는데 그 중 비용이 가장 작은 g=2를 선택한다. 결국 r,g,b모두다 계산해보면

 

마지막 테이블은 아래와 같이 나온다.

i=2

102

201

3

 

 

이처럼 중간부터 최소비용이 되는 애들을 더해가면서 마지막 집까지 구해주는 방식이다.

 

코드는 아래와 같다.

N=int(input())
costs=[list(map(int, input().split())) for _ in range(N)]

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])

print(min(costs[N-1]))

 

예전에 공부했었던 것 같은데,,, 하 왜 기억이 안날까ㅜ