백준 1149번: RGB거리 (파이썬)

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

1149번: RGB거리

 

문제

 

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

 

출력

 

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

 

풀이

 

처음에는 DP로 풀어야 하는 문제라고 생각했는데, 생각해보니 메모리를 그렇게 많이 사용하지 않아도 되는 문제로 보였다.

1번 집부터 N번 집까지 순서대로 집의 색상을 결정한다고 하면, 바로 이전 집의 색상하고만 다르면 된다고 생각했다. 이 아이디어를 구현하기 위해 last_r, last_g, last_b 변수를 사용하였다. 해당 변수들은 각각 이전 집에서 빨강, 초록, 파랑으로 색칠했을 때 이전 집까지의 비용의 최솟값을 저장하는 변수다. 예를 들어 last_r은 이전 집을 빨강으로 색칠했을 때 이전 집까지의 비용의 최솟값을 의미한다. 이제 각각의 집에 각각의 색상으로 칠하는 비용을 입력 받고, 이번에 색칠하는 색상이 아닌 다른 색상의 이전 집까지의 비용의 최솟값 중 더 작은 값을 더하여 last_r, last_g, last_b를 업데이트한다. 예를 들어 이번 집을 빨강으로 색칠한다면 last_g, last_b 값 중 더 작은 값에 이번 집을 빨강으로 색칠하는 비용을 더하는 방식이다.

해당 방식으로 n번 집까지 색칠을 완료한 후에, 세 값 중 가장 작은 값을 출력하면 문제는 해결된다.

 

소스 코드

import sys
input = sys.stdin.readline

n = int(input())
last_r, last_g, last_b = 0, 0, 0
for i in range(n):
    r, g, b = map(int, input().split())
    r += min(last_g, last_b)
    g += min(last_r, last_b)
    b += min(last_r, last_g)
    last_r, last_g, last_b = r, g, b
print(min(last_r, last_g, last_b))