[python] 1149. RGB거리

• 문제 

---

 

• 잘못된 풀이

import sys
n = int(input())

dp = [0] * n
for i in range(n):
    home_list = list(map(int, sys.stdin.readline().split()))
    tmp = home_list[:]
    if i != 0:
        del tmp[idx]
    dp[i] = min(tmp)
    idx = home_list.index(dp[i])
print(sum(dp))

 

해당 문제에서 제공한 규칙의 알고리즘은 '이전 집과 색깔이 겹치지 않으면' 된다.

 

따라서 내가 (잘못) 생각한 방법은 다음과 같다.

첫번째 집: 일단 첫번째 집에서 가장 작은 값을 찾는다. 그 다음 집과 색깔이 겹치지 않도록 index를 찾아 저장한다.

두번째 집 ~ : 앞 집의 index를 제외한 나머지 색깔 중에 가장 작은 값을 찾는다.

 

하지만 이와 같은 방법은 두 가지 문제점이 있음을 발견했다.

1. 3가지 색깔이 모두 같은 비용일 때의 처리를 해주지 않는다는 것이다.

2. 첫번째 집에서의 최솟값이 최종적으로 가장 작은 값을 갖는다는 보장이 없다는 것이다.

 

따라서 위와 같은 문제풀이는 잘못되었음을 알게되었다.

 

 

 

• 올바른 풀이

import sys
n = int(input())

RGB = []
for i in range(n):
    RGB.append(list(map(int, sys.stdin.readline().split())))

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

 

내가 생각했던 방법과는 조금 다르게,

위와 같은 풀이방법은 i번째를 기준으로 i-1를 보고 최솟값을 찾는다.

 

i번째 기준으로, 색깔이 다른 i-1번째의 값 중에 작은 값을 선택하여 마지막까지 더한다.

마지막까지 더하고 세 가지 색깔중에 가장 작은 값을 정답 !