[python] 백준 1149 RGB 거리

백준 1149 - RGB 거리 [SILVER 1]

N개의 집이 일자형으로 배치된 집이 있다.

집은 Red, Green, Blue 중 하나의 색으로 칠할 수 있다.

n번째 위치의 집에 페인트를 칠할 때 필요한 비용이 N개의 입력으로 들어온다.

징징이 맨션처럼 똑같은 색은 피하고 싶은 것인지, 양 옆 집(양 끝은 인접한 한 집)과 색깔이 겹치면 안 된다고 한다.

순차적으로 칠한다고 할 때, 이전에 칠한 색과 겹치지 않으면 된다는 것이다.

Greedy?

[23, 11, 34] 형태로 주어진 RGB 값을 [(23, 0), (11, 1), (34, 2)]와 같이 인덱스를 매긴 뒤 정렬시켰다.

[(11, 1), (23, 0), (34, 2)]와 같이, 가장 적은 비용이 드는 경우가 앞으로 온다.

가능하면 앞에 있는 번호를 선택하되, 이전에 고른 번호와 같은 경우 그 뒤의 값을 고르기는 방식이다.

당연히 실패한다.

앞부터 가장 작은 값을 찾기 때문에,

[(10, 0), (20, 1), (30, 2)] 에서 0번째를 선택할 경우 다음 번째에서

[(1, 0), (1000, 1), (1000, 2)] 와 같은 극단적인 경우에서 막대한 비용을 손해봐야하기 때문이다.

브루트 포스

또 말도 안 되는 방법이다.

간단히 해서, 최대 3^n (n은 집의 수) 시간 복잡도가 필요하다.

만약 최선과 최악의 차가 1000(비용의 최대값)이상인 경우를 쳐낸다고 해도 시간 제한을 충족하기엔 한참 모자르다.

DP?

처음엔 어떻게 해야하나 쩔쩔 매는 게 DP문제의 매력인 것 같다.

이게 DP가 맞는지도 모르겠지만…

각 행의 노드마다 최솟값을 저장해두고 끝까지 달려야 한다.

1, 2, 3
5, 4, 3
2, 2, 2
1, 3, 2
7, 8, 9

3번째 집(2, 2, 2)에 다다랐다고 가정하자.

첫 번째와 두 번째는 어떻게 진행해왔을까? 그리고 세 번째는 어떤 값을 칠해야 할까?

만약 세 번째 집을 R로 칠한다고 가정하면, 세 번째 집에 도달하는 경우는 네 개가 된다.

R-G-R, R-B-R, G-B-R, B-G-R

해당 네 개의 경우 중, 가장 작은 값을 세 번째 집 R칸에 저장하자.

그리고 세 번째 집의 G와 B도 똑같은 방식으로 저장해두자.

1, 2, 3
5, 4, 3
7, 6, 7 <-- (2, 2, 2)
5, 1, 5
7, 8, 9

각각 R-G-R, R-B-G, R-G-B로 도착했다.

아까 말했듯, 중요한 건 직전에 칠한 집의 색이다.

그렇기 때문에 이번에는 여섯 번째 집까지가 아닌, 방금 계산한 세 번째 집을 포함하여 네번 째와 다섯 번째 집까지를 계산해야 한다.

---
7, 6, 7
5, 1, 5
15, 19, 17 <-- (7, 8, 9)

각각 R(B)-G-R, G-R(B)-G, R-G-B로 도착했다.

세 번째 집에서 G을 선택한 경우, 네 번째에서 1을 선택하지 못해 최대값이 나올 수밖에 없게 된다.

이러한 경우가 많으므로, 가지를 치지 않고 모든 경우를 계산한 뒤 저장해야 한다.

이렇게 될 경우 3+(n*2)행에서는 해당 칸에 도착하기 위한 가장 적은 값이 저장된다.

정답 코드

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

# 각각 R, G, B로 도착한 경우의 수
order1 = ((0,2,0),(0,1,0),(1,2,0),(2,1,0))
order2 = ((1,2,1),(1,0,1),(0,2,1),(2,0,1))
order3 = ((0,1,2),(1,0,2),(2,0,2),(2,1,2))

# 시작값 셋팅
f, s, t = rgb[0]
n = 3
for x in range(1, N//2+1):
    
    # 마지막 집이 짝수일 경우
    if x == N//2 and not N%2:
        n = 2
    
    # 이전에 계산한 값 + 다음 두 경우
    arr = [[f,s,t]] + rgb[x*2-1:x*2+1]
    f_l, s_l, t_l = [], [], []

    # 각 경우의 수 계산
    for i in range(4):
        f, s, t = 0, 0, 0
        for j in range(n):
            f += arr[j][order1[i][j]]
            s += arr[j][order2[i][j]]
            t += arr[j][order3[i][j]]
        f_l.append(f)
        s_l.append(s)
        t_l.append(t)
    
    # 최소값 저장
    f, s, t = min(f_l), min(s_l), min(t_l)  

print(min([f,s,t]))

결과

메모리	시간
31120KB	44ms