[백준] 1149번 RGB 거리

단계별로 풀어보기 동적계획법1의 5단계 문제

1149번: RGB거리

이렇게 제출했는데 런타임 에러가 났다

def promising(row, color):
    if row == 0:
        return True
    if col[row - 1] == color:
        return False
    else:
        return True
def locate(row):
    if row == n:
        total.append(cost[row - 1])
        return
    for i in range(3):
        if promising(row, i):
            col[row] = i
            cost[row] = cost[row - 1] + li[row][i]
            locate(row + 1)
n = int(input())
li = []
from sys import stdin
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
col = [0] * n
cost = [0] * n
total = []
locate(0)
print(min(total))

 

5일 뒤 2020.01.18 재도전

1932번을 풀고 나니까 이 문제도 어떻게 푸는지 딱 보였다.

이렇게 쉽게 풀 수 있었는데 괜히 시간 낭비를 한 것 같지만 덕분에 또 하나 더 배웠다. 앞으로는 절대로 잊지 말아야지

 

1932번과 같이 뒤에서부터 풀면 된다.

n = int(input())
li = []
from sys import stdin
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
for i in range(n - 2, -1, -1):
    for j in range(3):
        if j == 0:
            li[i][j] = min(li[i][j] + li[i + 1][1], li[i][j] + li[i + 1][2])
        elif j == 1:
            li[i][j] = min(li[i][j] + li[i + 1][0], li[i][j] + li[i + 1][2])
        else:
            li[i][j] = min(li[i][j] + li[i + 1][0], li[i][j] + li[i + 1][1])
print(min(li[0]))