[ BOJ 1149 ] RGB거리(Python)

문제

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

n개의 집들을 퐁당퐁당 다른 색으로 칠하는 문제이다.
(n-1)과 (n) / (n)과 (n+1)은 색이 달라야한다.
각 집마다 색을 칠하는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하면 된다. 🌈

처음 문제를 접했을 때 굉장히 쉽다고 느꼈는데 코드상으로 구현을 못해서 눈물을 흘렸었고,
생각하지 못했던 이외의 경우가 있어서 눈물을 또 한번 흘렸다.

문제 풀이

잘못된 풀이 🤬

1. 첫번째 집의 색상을 칠할 때, 가장 저렴한 색을 고른다.
2. 이전 집과 색상이 겹치지 않는 두가지 색 중 더 저렴한 색을 고른다.
3. 마지막까지 반복한다.

이 풀이가 왜 틀렸냐,,

🔥 지금 당장의 최적의 해가 최종적으로는 최적의 해가 아닐 수 있기 때문이다. (aka 그리디 알고리즘)

반례

2
#R  G  B
100 1 100
900 1 900

두 개의 집이 있을 때, 첫번째 집의 색상은 가장 저렴한 G로 칠해준다 (1)
그럼 두번째 집의 색상은 R(900) 또는 B(900)로 칠해줘야한다. 그러면 901이 출력된다.

아뿔싸 최적의 해가 아니다 👁👄👁

첫번째 집의 색상을 R(100)이나 B(100)로 칠해야만, 두번째 집에서 G(1)를 고르고 최종적으로 최적의 해인 101을 얻을 수 있다.

따라서 첫번째 집을 3가지 색상 모두 고려해줘야 하는 것이다.

올바른 풀이 😎

각 집에 대해서 색상을 칠한 값을 저장해줄 memo 리스트를 만들어주었다.

memo = [[] for _ in range(n)]
memo[0] = colors[0] #첫번째 집의 RGB 가격

그리고 두번째 집부터 세가지 색상을 칠했을 때의 상황을 고려해주었다.

for i in range(1,n):
    memo[i] = [
    	# 이전 집과 색상이 겹치지 않도록 해준다.
        colors[i][0] + min(memo[i-1][1],memo[i-1][2]),
        colors[i][1] + min(memo[i-1][0],memo[i-1][2]),
        colors[i][2] + min(memo[i-1][0],memo[i-1][1]),
    ]

결과적으로 memo 리스트의 n-1번째 칸에는

[ 
첫번째 집을 R로 칠했을 때 결과값, 
첫번째 집을 G로 칠했을 때 결과값, 
첫번째 집을 B로 칠했을 때 결과값
] 

다음과 같이 담겨있을 것이다.
이 중 가장 작은 값을 출력해주면 된다.

코드

import sys
input = sys.stdin.readline

n = int(input().rstrip())
colors = []

for i in range(n):
    RGB = list(map(int,input().rstrip().rsplit()))
    colors.append(RGB)

memo = [[] for _ in range(n)]
memo[0] = colors[0]

#f(n) = min (
# f(r) + min[f(n-1,b),f(n-1,g) ,
# f(g) + min[f(n-1,r),f(n-1,b) ,
# f(b) + min[f(n-1,r),f(n-1,g)]
#)

for i in range(1,n):
    memo[i] = [
        colors[i][0] + min(memo[i-1][1],memo[i-1][2]),
        colors[i][1] + min(memo[i-1][0],memo[i-1][2]),
        colors[i][2] + min(memo[i-1][0],memo[i-1][1]),
    ]

print(min(memo[n-1]))