[BOJ] 1149 - RGB거리

[BOJ] 1149 - RGB거리

문제

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

출력

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

예제 입력

3
26 40 83
49 60 57
13 89 99

예제 출력

96

문제 해결

이 문제를 읽었을 때 키워드는 DP로 되어 있고 최소의 금액을 구하는 것이므로 list 에 최소값을 계속 넣는 방식으로 접근하면 되겠다고 생각했었다. 그럼 일단 최소 금액을 구하는 방식을 생각해보자.

n번째 집의 R의 최소금액 = min(n-1 집의 G 최소금액, n-1 집의 B 최소금액) + n번쨰 R의 금액

처음에는 생각을 현재 정한 색을 다음 인덱스에서 샌택하지 않고 다음 최소값을 구하는 로직을 생각했었는데 필터링 해야하는 조건들이 너무 많고 정확하지 않은 답이 나와, 조금 생각을 바꿔보았다.

내가 만약 R을 골랐다면 나의 전 집의 색깔은 G, B 중에 하나 라는 조건을 토대로 전 집의 G, B 의 최소 금액을 구해 현재 나의 R 값을 더해주면 그 색의 최소 금액 산출되었다. 마지막 집을 R, G, B 로 그렸을 때의 최소금액만 따지면 그 앞에 어떤 색으로 집을 칠했는지 판별하지 않아도 최소값이 구해진다. 코드로 옮겨보자.

python 코드

n = int(input())
cost1 = [0] * (n+1)
cost2 = [0] * (n+1)
cost3 = [0] * (n+1)

for i in range(1, n+1):
    r, g, b = map(int, input().split())
    if i == 1 :
        cost1[i] = r
        cost2[i] = g
        cost3[i] = b
    else :
        cost1[i] = min(cost2[i-1], cost3[i-1] )+ r
        cost2[i] = min(cost1[i-1], cost3[i-1] )+ g
        cost3[i] = min(cost2[i-1], cost1[i-1] )+ b

print(min(min(cost1[n], cost2[n]), cost3[n]))

느낀점

어떤 문제를 풀떄 무조건 조건을 세우기 보다 조금 더 현명한 방법으로 푸는 방법이 있는지 알아보는 것도 중요하는 것을 배웠다.