백준 1149번 - RGB거리

RGB를 같은 색이 반복되지 않게 나열하는 문제다. i번째 집의 색을 각각 빨강(0), 초록(1), 파랑(2)으로 칠하는 비용을 갱신해주면서 반복해주면 된다. i번째 집의 색을 빨강으로 칠한다면, i-1번째 집의 색을 초록, 파랑으로 칠하는 비용 중에서 더 작은 값을 칠해주면 되기 때문에 파이썬의 기본 함수 min을 사용하여 구해준 뒤, i번째 집을 빨강으로 칠하는 비용을 더해줘서 갱신을 해준다. 그 뒤 i+1번째도 같은 원리로 갱신이 되고 결국 N번째에는 각 최소 비용이 들어갈 것이기 때문에 그 3개 중에 최솟값을 찾아주면 된다.

 

##변수 선언 부분##
cost = []

##메인 함수 부분##
if __name__ == "__main__":
    N = int(input())
    cost = [[int(x) for x in input().split()]for _ in range(N)]
    for i in range(1,N): #cost의 값을 갱신해주면서 반복해준다.
        cost[i][0] = min(cost[i - 1][1], cost[i - 1][2]) + cost[i][0]
        cost[i][1] = min(cost[i - 1][0], cost[i - 1][2]) + cost[i][1]
        cost[i][2] = min(cost[i - 1][1], cost[i - 1][0]) + cost[i][2]

    print(min(cost[N-1][0],cost[N-1][1],cost[N-1][2]))

이 문제가 DP문제가 아니었으면 쉽게 풀었겠지만, DP문제이다보니 정답을 맞혀도 시간 초과 때문에 시간을 오래 썼다. 처음엔 단순히 백트래킹 방식으로 prunning을 잘해주면 시간 초과가 안뜰 수도 있겠구나 싶었다. 지금까지 계산한 값이 min 보다 크면 바로 탈출하는 식으로 코드를 썼지만 시간 초과가 떠서 근본적인 문제가 있거니 하고 코드를 다 지웠다. 

DP에서 Top-down방식으로 재귀 함수를 쓰는 일은 드문 것 같다.