BOJ 1149 RGB 거리 python

 

문제의 조건은 한 마디로, 1번부터 N번까지의 집이 이전 집과 다른 색깔이어야 한다는 것이다. 이 때 각 색을 칠하는 데 드는 비용이 다를 때 모든 집을 칠하기 위한 최소 비용을 구해야 한다.

기

n-1번째까지 최소 비용을 구할 수 있다면, 마지막 n번째 최소 비용을 더함으로써 쉽게 답을 구할 수 있을 거라는 생각이 들었다. 

승

하지만 어떻게? 지금까지 풀었던 기본적인 dp 문제들은 일차원 리스트에 간단하게 점화식의 항들을 작성할 수 있었는데, 이 문제는 조금 더 생소했다. 지금까지 풀었던 것과 동일한 방식으로 풀 수가 없는 문제였다.

고민을 거듭한 결과, n번째 집을 칠하는 최소 비용은 n-1 번째 최소 비용 후보들의 최솟값으로써 결정된다는 사실을 알아냈다. 그러기 위해서는 메모리를 조금 다른 방식으로 활용해야 했다.

전

그렇다면 어떻게 해야할까? 답은 이차원 리스트에 있었다.

 

n번째 집이 빨간색으로 칠해지는 경우, n-1번째 집은 초록색 혹은 파란색으로 칠해져야 한다.

n번째 집이 초록색으로 칠해지는 경우, n-1번째 집은 빨간색 혹은 파란색으로 칠해져야 한다.

n번째 집이 파란색으로 칠해지는 경우, n-1번째 집은 빨간색 혹은 초록색으로 칠해져야 한다.

 

그렇다면, 다음과 같이 이차원배열이 초기화될 수 있다.

dp[0]	R0	G0	B0
dp[1]	min(R1+G0, R1+B0)	min(G1+R0, G1+B0)	min(B1+R0, B1+G0)
...
dp[n-1]	Rn-1	Gn-1	Bn-1
dp[n]	min(Rn+Gn-1, Rn+Bn-1)	min(Gn+Rn-1, Gn+Bn-1)	min(Bn+Rn-1, Bn+Gn-1)

결

메모리를 어떻게 활용할 지 계획을 세우는 게 어려웠고, 구현은 간단한 문제였다. 

 

이런 식으로 도식화해서 풀어보니 한 결 수월했다. 구현은 다음과 같다.

---

코드

x = int(input())
l = []
R,G,B = [],[],[]
for _ in range(x):
    r,g,b = map(int,input().split())
    R.append(r)
    G.append(g)
    B.append(b)

for i in range(1,x):
    R[i] = min(R[i] + G[i-1], R[i] + B[i-1])
    G[i] = min(G[i] + R[i-1], G[i] + B[i-1])
    B[i] = min(B[i] + R[i-1], B[i] + G[i-1])

print(min(R[x-1],G[x-1],B[x-1]))