BOJ : 1149 RGB거리 (파이썬)

문제

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

1149번: RGB거리

풀이

일단 문제의 조건을 잘 이해해야 한다.

조건

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

이 조건을 생각하면 무조건적으로 1번집과 2번집은 같은색은 안되고 연속적으로 같은 색을 칠할 수 없는것을 알게 된다.

그래서 리스트를 계속해서 최신화해주면서 누적값을 구해주면 문제를 풀 수 있다.

예시

입력5를 예시로 들어보겠습니다.

30	19	5
64	77	64
15	19	97
4	71	57
90	86	84
93	32	91

---

첫번째 연산 후

30	19	5
35	82	83
15	19	97
4	71	57
90	86	84
93	32	91

---

두번째 연산 후

30	19	5
35	82	83
97	88	166
4	71	57
90	86	84
93	32	91

---

이런식으로 반복하다 보면 최종적으로

30	19	5
35	82	83
97	88	166
92	168	145
235	178	176
269	208	269

라는 값을 얻을 수 있다.

소스코드

import sys

n = int(sys.stdin.readline())

g = []

for i in range(n) :
    s = list(map(int, sys.stdin.readline().split()))
    g.append(s)

#빨강 초록 파랑으로 다 칠해줘야함

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

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

감사합니다.