https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
n = int(input())
a = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]
d = [[0, 0, 0] for _ in range(n + 1)]
for i in range(1, n + 1):
d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1]
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2]
print(min(d[n][0], d[n][1], d[n][2]))
RGB 거리, R = 0, G = 1, B = 2 라고 하고
A[i][j] = i번 집이 j번색일 경우 로 가정하자.
1. i의 이웃은 i - 1, i + 1
2. 첫 집과 마지막 집은 이웃이 아니다.
3. 모든 이웃은 다른 색의 집이다.
- 연속하는 집을 같은 색으로 칠할 수 없다.
d[i][0] = min(d[i - 1][1], d[i-1][2]) + a[i][0]
d[i][1] = min(d[i - 1][0], d[i-1][2]) + a[i][1]
d[i][2] = min(d[i - 1][0], d[i-1][1]) + a[i][2]
정답 : min(d[n][0], d[n][1], d[n][2])
'백준 알고리즘 (Baekjoon Algorithm)' 카테고리의 다른 글
| [파이썬 (풀이추가예정)] 백준 알고리즘 No.11054 가장 긴 바이토닉 부분 수열 (0) | 2022.01.17 |
|---|---|
| [파이썬] 백준 알고리즘 No.1309 동물원 (0) | 2022.01.15 |
| [파이썬] 백준 알고리즘 No.2225 합분해 (0) | 2022.01.13 |
| [파이썬] 백준 알고리즘 No.14391 종이 조각 (0) | 2022.01.10 |
| [파이썬] 백준 알고리즘 No.10819 차이를 최대로 (0) | 2022.01.08 |