1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
[알고리즘]
DP
[접근 방법]
1. 점화식 세우기
* i-1번째 집과 i번째 집의 관계 → 조건은 서로 다른 색
* 최소비용 구하기 →min으로 비교
2. 경우의수 생각
* i번째 집이 R, G, B인 경우 3가지
[코드]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
N = int(input())
cost = []
for i in range(N) :
cost.append(list(map(int, input().split())))
print(cost)
for i in range(1, N) :
# 0, 1, 2는 각각 R, G, B
# i번째 집을 0으로 칠하면, i-1번째 집은 1 or 2
cost[i][0] = cost[i][0] + min(cost[i - 1][1], cost[i - 1][2])
cost[i][1] = cost[i][1] + min(cost[i - 1][0], cost[i - 1][2])
cost[i][2] = cost[i][2] + min(cost[i - 1][1], cost[i - 1][0])
print(min(cost[N - 1][0], cost[N - 1][1], cost[N - 1][2]))
|
cs |
'Algorithm > Dynamic Programming' 카테고리의 다른 글
| [Algorithm/Java] 다이나믹 프로그래밍 복습 (0) | 2022.07.14 |
|---|---|
| [Python] 백준 #11052 카드 구매하기 (0) | 2021.06.30 |
| [Python] 백준 #1932 정수 삼각형 (0) | 2021.06.30 |