[백준] 1149 RGB 거리

백준 1149 RGB 거리

문제

RGB 거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고 1번 집부터 N번 집까지 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.

각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때 아래 규칙을 만족하며 모든 집을 칠하는 비용의 최솟값을 구하시오

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번째 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

• 첫 번째 줄: 집의 수 N
• 두 번째 줄 ~ : 각 집을 빨강, 초록, 파랑으로 칠하는 비용

출력

모든 집을 칠하는 비용의 최솟값을 출력한다.

해결 방식

dp

• dp 배열에 해당 집을 빨, 초, 파로 칠할 경우 각각의 최소 값을 저장한다.
  • 이 3가지 색으로 칠한 경우 중 최소값을 사용한다.

예시

1번째 집 색칠 비용: 1, 100, 100 2번째 집 색칠 비용: 100, 1, 100 3번째 집 색칠 비용: 100, 100, 1

1. 2번째 집 색칠

   • 빨간색으로 색칠하는 경우

     – 1번째 집 색이 초록 or 파랑

     – 100, 100 중 최솟값 선택 = 100

     – 200

   • 초록색으로 색칠하는 경우

     – 1번째 집 색이 빨강 or 파랑

     – 1, 100 중 최솟값 선택 = 1

     – 2

   • 파랑색으로 색칠하는 경우

     – 1번째 집 색이 빨강 or 초록

     – 1, 100 중 최솟값 선택 = 1

     – 101

2. 3번째 집 색칠

   • 빨간색으로 색칠하는 경우

     – 2번째 집 색이 초록 or 파랑

     – 2, 101 중 최솟값 선택 = 2

     – 102

   • 초록색으로 색칠하는 경우

     – 2번째 집 색이 빨강 or 파랑

     – 101, 101 중 최솟값 선택 = 101

     – 201

   • 파랑색으로 색칠하는 경우

     – 2번째 집 색이 빨강 or 초록

     – 101, 2 중 최솟값 선택 = 2

     – 3

∴ 색칠 최소 비용 = 3

코드

n = int(input())
colors = [list(map(int, input().split())) for _ in range(n)]

for i in range(1, n):
    colors[i][0] = min(colors[i-1][1], colors[i-1][2]) + colors[i][0]
    colors[i][1] = min(colors[i-1][0], colors[i-1][2]) + colors[i][1]
    colors[i][2] = min(colors[i-1][0], colors[i-1][1]) + colors[i][2]

print(min(colors[-1][0], colors[-1][1], colors[-1][2]))