[알고리즘]
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 |