알고리즘
[알고리즘] 백준 파이썬 1149 RGB거리
chaewonni
2025. 1. 12. 23:36
📍 문제 탐색하기
이번 문제는 RGB거리의 집들을 칠하는 데 최소 비용을 구하는 문제이다.
주어진 규칙에 따라 인접한 집들의 색이 같지 않도록 칠해야 하며, 각 집을 빨강(R), 초록(G), 파랑(B)으로 칠하는 비용이 주어진다.
문제 조건
- 집의 수 N (2≤N≤1,000)
- 각 집의 칠하는 비용은 1,000 이하의 자연수로 주어짐.
- 규칙:
- 1번 집의 색은 2번 집과 같지 않아야 한다.
- i번 집의 색은 (i−1)(번 및 (i+1)번 집과 같지 않아야 한다.
- N번 집의 색은 (N−1)번 집과 같지 않아야 한다.
입출력
- 입력:
- 첫 줄에 집의 수 N
- 이후 N개의 줄에 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 순서대로 주어짐.
- 출력:
- 모든 집을 칠하는 데 드는 최소 비용.
📍 코드 설계하기
입력 처리
- 집의 개수 N을 입력받는다.
- 각 집을 빨강, 초록, 파랑으로 칠하는 비용을 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번째 집은 빨강 또는 초록이어야 하므로 그 중 최소 비용을 더한다. - 초기값: 첫 번째 집의 비용은 이미 주어진 그대로 사용한다.
구현
- 두 번째 집부터 시작하여 각 집을 칠하는 최소 비용을 계산한다.
- 마지막 집(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]))