CodeDrive

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

우선 입력으로 들어온 값들을 이차원 배열꼴로 만들어준다. 그리고 난 뒤 0번째 행부터가 아닌 1번째 행부터 각 원소에 대해 전 행에서 자신의 열과 다른 값들중 최솟값을 더해준다. 이를 계속 누적해서 끝 행까지 반복하고 최종적으론 끝 행의 최솟값을 반환하도록 한다.