RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
모든 경우의 수를 따로 저장한다고 생각하면 접근하기 힘들 수 있다. 빨간색, 초록색, 파란색을 칠하는 비용이 각각 리스트에 저장이 되어있기 때문에, 이들을 선택하였을 때, 최선의 선택을 리스트에 업데이트해 나가면 쉽게 풀 수 있다.
첫번째 줄에는 빨간색[0][0], 초록색[0][1], 파란색[0][2]을 칠하는데 필요한 비용이 들어있다. 이것을 활용하면 된다.
이러한 작업을 쭉 이어나간 다음, 제일 마지막에 나온 값들 중에서 최솟값을 고르게 된다면 그게 최소 비용이 될 것이다.
N = int(input())
RGB = []
for i in range(N):
RGB.append(list(map(int, input().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]))