1. 첫번째 풀이 - 오답

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

dp = [-1] * 99999

min_ = 99999999 # 첫번째 집의 최솟값과 선택한 색깔을 구한다.
for i in range(3):
    if min_ > colors[0][i]:
        min_ = colors[0][i]
        sum_ = min_
        dp[0] = i
        
for n in range(1, N): # 두번째 집부터 색깔을 구한다.
    min_ = 99999999
    for i in range(3):
        if i != dp[n-1]: # 앞 집의 색깔을 피한다.
            if min_ >= colors[n][i]:
                min_ = colors[n][i]
                dp[n] = i # 색깔의 종류를 저장한다.
    sum_ += min_ # 값 누적

print(sum_) # 출력

10
6 7 1
10 3 4
9 1 9
5 2 3
3 3 6
1 10 2
9 7 1
10 8 1
4 1 8
10 9 2
31

위와 같은 풀이는 n-1 번째에서 중복되는 값이 발생할 경우,

n 번째 집의 최솟값을 구할 때 오류가 발생한다.

예를 들어 3번째 행에서 9 1 9 로 0번째 2번째 index에서 중복이 발생하는데,

iteration을 앞에부터 뒤로 진행하므로 dp[3]에 2가 저장 된다.

이때, 4번째 행에서 5 2 3으로 최솟값 3을 고를 수 있지만, dp[3] = 2 이므로,

2번째 index를 피해 0번째 값인 5가 선택되는 오류가 발생한다.

2. 두번째 풀이

• concept은 R, G, B 각각의 경우로 나누어 메모이제이션 공간을 생성하고,
• 색깔은 겹치지 않으면서 최솟값을 누적계산해나간다.

$R_n = Min(G_{n-1}, B_{n-1}) + R_n$
$G_n = Min(R_{n-1}, B_{n-1}) + G_n$
$B_n = Min(G_{n-1}, R_{n-1}) + B_n$

• 이를 python 문법으로 나타내면 다음과 같다

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

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

10
6 7 1
10 3 4
9 1 9
5 2 3
3 3 6
1 10 2
9 7 1
10 8 1
4 1 8
10 9 2

print(min(colors[n]))

29

• 섣불리 코드를 짜기보다는 발생할 수 있는 예외 상황에 대해 꼼꼼히 생각하고 따져보는 습관을 길러야 겠다.