문제
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
풀이
어떤 시점 i에서 고를 수 있는 색은 총 세가지가 있으므로, 세 가지 색에 대해서 비용이 최소가 되게끔 dp를 작성하면 된다.
N = int(input())
rgb = [[]]
for _ in range(N):
rgb.append(list(map(int,input().split())))
dp = [[0]*3 for _ in range(N+1)]
for i in range(1,N+1):
for j in range(3):
dp[i][j] = min([dp[i-1][k]+rgb[i][j] for k in range(3) if k != j])
print(min(dp[N]))
'PS > 백준' 카테고리의 다른 글
| 1463번 - 1로 만들기 (0) | 2022.10.22 |
|---|---|
| 2579번 - 계단 오르기 (0) | 2022.10.21 |
| 1912번 - 연속합 (0) | 2022.10.21 |
| 17822번 - 원판 돌리기 (0) | 2022.10.12 |
| 15686번 - 치킨 배달 (0) | 2022.10.10 |