1149 RGB거리

이전에 집을 어떤 색으로 칠했냐에 따라 다음 집에 칠할 색이 나눠집니다. 때문에, N번째 집까지 계산한 결과를 통해서 N + 1번째 집까지의 답을 계산해낼 수 있습니다.

각 집에 대해서, 3가지 선택지가 존재합니다.

• 빨강으로 칠할 때
  • 이전 집을 초록이나 파랑으로 칠할 수 있습니다.
• 초록으로 칠할 때
  • 이전 집을 빨강이나 파랑으로 칠할 수 있습니다.
• 파랑으로 칠할 때
  • 이전 집을 빨강이나 초록으로 칠할 수 있습니다.

전체 경우에서 최소 비용을 구하는 것이기 때문에, 다음과 같이 계산할 수 있습니다.

• N번째 집의 최소 비용 [빨강] = min( N - 1번째 집의 최소 비용 [초록], N - 1번째 집의 최소 비용[파랑] ) + N번째 집에 빨강을 칠하는 비용
• N번째 집의 최소 비용 [초록] = min( N - 1번째 집의 최소 비용 [빨강], N - 1번째 집의 최소 비용[파랑] ) + N번째 집에 초록을 칠하는 비용
• N번째 집의 최소 비용 [파랑] = min( N - 1번째 집의 최소 비용 [빨강], N - 1번째 집의 최소 비용[초록] ) + N번째 집에 파랑을 칠하는 비용

구하는 결과는 마지막 집의 [빨강] [초록] [파랑] 중 최솟값이 됩니다.