[알고리즘] 백준 파이썬 1149 RGB거리

 

📍 문제 탐색하기

이번 문제는 RGB거리의 집들을 칠하는 데 최소 비용을 구하는 문제이다.
주어진 규칙에 따라 인접한 집들의 색이 같지 않도록 칠해야 하며, 각 집을 빨강(R), 초록(G), 파랑(B)으로 칠하는 비용이 주어진다.

문제 조건

1. 집의 수 N (2≤N≤1,000)
2. 각 집의 칠하는 비용은 1,000 이하의 자연수로 주어짐.
3. 규칙:
   • 1번 집의 색은 2번 집과 같지 않아야 한다.
   • i번 집의 색은 (i−1)(번 및 (i+1)번 집과 같지 않아야 한다.
   • N번 집의 색은 (N−1)번 집과 같지 않아야 한다.

입출력

• 입력:
  • 첫 줄에 집의 수 N
  • 이후 N개의 줄에 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 순서대로 주어짐.
• 출력:
  • 모든 집을 칠하는 데 드는 최소 비용.

---

📍 코드 설계하기

입력 처리

1. 집의 개수 N을 입력받는다.
2. 각 집을 빨강, 초록, 파랑으로 칠하는 비용을 rgb_list에 저장한다.

점화식 설계

• DP 정의
  rgb_list[i][j]는 i번째 집을 j색으로 칠했을 때 최소 비용을 의미한다.
  (j는 0=빨강, 1=초록, 2=파랑)
• 점화식
  rgb_list[i][0] = rgb_list[i][0] + min(rgb_list[i-1][1], rgb_list[i-1][2])
  → i번째 집을 빨강으로 칠했을 때, i-1번째 집은 초록 또는 파랑이어야 하므로 그 중 최소 비용을 더한다.
  rgb_list[i][1] = rgb_list[i][1] + min(rgb_list[i-1][0], rgb_list[i-1][2])
  → i번째 집을 초록으로 칠했을 때, i-1번째 집은 빨강 또는 파랑이어야 하므로 그 중 최소 비용을 더한다.
  rgb_list[i][2] = rgb_list[i][2] + min(rgb_list[i-1][0], rgb_list[i-1][1])
  → i번째 집을 파랑으로 칠했을 때, i-1번째 집은 빨강 또는 초록이어야 하므로 그 중 최소 비용을 더한다.
• 초기값: 첫 번째 집의 비용은 이미 주어진 그대로 사용한다.

---

구현

1. 두 번째 집부터 시작하여 각 집을 칠하는 최소 비용을 계산한다.
2. 마지막 집(N번 집)의 빨강, 초록, 파랑으로 칠한 비용 중 최소값을 출력한다.

---

📍 시도 회차 및 수정 사항

1차 시도 (맞음) ✅

import sys

N = int(sys.stdin.readline())
rgb_list = []

for i in range(N):
    rgb_list.append(list(map(int, input().split())))

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

print(min(rgb_list[N-1][0], rgb_list[N-1][1], rgb_list[N-1][2]))

---

📍 느낀점

DP는 미래의 결정이 아니라, 현재까지의 최적 상태를 기반으로 점진적으로 해를 만들어 간다.