[BOJ | Python] 1149번: RGB거리

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

 

 

문제

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보다 작거나 같은 자연수이다.

 

출력

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

 

풀이

https://haerxeong.tistory.com/19

[BOJ] 9465번: 스티커

 

어떻게 풀지 한참을 고민하던 중, 예전에 푼 '스티커'라는 문제를 통해 해답을 얻었다. 

처음에는 dp라는 일차원 리스트에 최소 합을 저장해야겠다는 생각으로, 어떻게 해야 각 단계별 최솟값을 한 리스트에 넣을 수 있을까 고민했다.

그러나 위 문제의 풀이를 통해, 모든 경우에 대한 최솟값을 저장한 후, 최종적인 최솟값을 출력하면 되는구나!라는 해답을 얻을 수 있었다. 

 

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

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

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

 

입력값이 이처럼 n행 3열로 주어진다는 점을 생각해보면, 

- 2행의 1열까지의 최소합에 포함될 수 있는 1행의 값은 2열 또는 3열

- 2행의 2열까지의 최소합에 포함될 수 있는 1행의 값은 1열 또는 3열

- 2행의 3열까지의 최소합에 포함될 수 있는 1행의 값은 1열 또는 2열

 

이러한 방법으로 3열에 대한 모든 최소의 합을 구했다고 생각하면 된다.

그후 마지막 열에 대한 최솟값을 출력함으로써 답을 구한 것이다.

 

역시 DP는 쉽지 않다.🥹

DP를 풀 때는 '해당 값에 포함될 수 있는 전 단계의 값이 어느것인지!'를 파악하도록 노력해야겠다.