[백준/파이썬] 1149 RGB거리

#문제링크

https://www.acmicpc.net/problem/1149

1149번: RGB거리

#나의풀이

import sys

if __name__=="__main__":
    N = int(sys.stdin.readline())
    board = []
    dp = [[0]* 3 for _ in range(N)]
    for _ in range(N):
        board.append(list(map(int, sys.stdin.readline().split())))
    dp[0] = board[0]

    for i in range(1, N):
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + board[i][0]
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + board[i][1]
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + board[i][2]
    print(min(dp[N-1]))

#해설

풀면서 좀 화가 났던 문제 확실히 DP를 많이 안풀어봐서 그런가 어떻게 풀어야 하는지 감도 안왔다.

크기는 N이 1000까지 있다 총 3가지 색깔이니까 조합으로 풀게되면 끔찍한 상황이 눈에 보였다. 

문제는 생각보다 간단했다 전에 사용한 색깔은 사용이 불가능하다 그러니 각 색깔마다 전에 최소값들을 비교하면서 더해가면 된다. 

코드로 설명하자면 0번째 배열의 빨강 초록 파랑은 가장 먼저 시작한 수이기때문에 0번째까지의 최소값이라고 할 수 있으니 dp[0]에 그대로 넣어주었다. 1번째 인덱스부터 빨강은 파랑과 초록이 올 수 있으며 이 두개중 작은값을 찾고 board[1]번째에 빨강값(현재값)을 더해준다. 초록도 똑같이 빨강과 파랑을 비교하고 현재 초록값을 더해준다. 파랑 이하동문

이렇게 마지막배열에서 최소값을 출력해주면 된다.