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

RGB거리

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	128 MB	72867	36485	27248	49.755%

문제

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://teching.tistory.com/
import sys

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

priceMemo = [0,0,0]
for i in range(n):
    nums = (list(map(int, sys.stdin.readline().split())))
    tmp = [0,0,0]
    tmp[0] = min(nums[0]+priceMemo[1], nums[0]+priceMemo[2])
    tmp[1] = min(nums[1]+priceMemo[0], nums[1]+priceMemo[2])
    tmp[2] = min(nums[2]+priceMemo[0], nums[2]+priceMemo[1])
    priceMemo = tmp

print(min(priceMemo))

해설

먼저 문제의 규칙을 살펴보자.

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

해당 규칙들을 전부 만족하면서 최솟값으로 색칠을 해야 한다.

규칙이 어려워 보이지만 단순하게 생각하면 N을 높여갈 때 N-1의 집과 색상을 다르게 칠하면 된다.

해당 규칙을 토대로 백트래킹을 통해서 풀어주면 더욱 쉽게 풀리지만 시간제한으로 인해 백트래킹을 사용할 수 없는 상황이다. 

그러므로 백트래킹이 아닌 동적 계획법을 이용해 풀어보도록 하였다.

동적계획법 중에서도 상향식 방향으로 구현하는 타뷸레이션을 활용하였다.

관련 내용은 https://teching.tistory.com/89 포스트에 들어가면 자세하게 확인할 수 있다.

동적 계획법 (파이썬)

내가 구현 방법을 간략하게 설명하자면

priceMemo는 현재 상태에서 각 색상을 칠했을 때의 경우의 최솟값이다.

tmp는 새롭게 칠할 때 빨강, 초록, 파랑 순으로 칠할 때의 최솟값을 구해준다.