https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
풀이 과정
d[i][k]를 총 i개의 집을 조건에 맞게 칠하는 비용의 최소값이되 마지막이 k로 칠해지는 경우라고 하자. (0 = 빨강, 1 = 초록, 2 = 파랑)
그러면 다음과 같은 점화식이 성립한다.
d[i][0] = min(d[i-1][1], d[i-1][2]) + p[i][0]
d[i][1] = min(d[i-1][0], d[i-1][2]) + p[i][1]
d[i][2] = min(d[i-1][0], d[i-1][1]) + p[i][2]
소스 코드
import sys
N = int(sys.stdin.readline())
d = [[0 for _ in range(4)] for _ in range(N+1)]
p = [[0, 0, 0]]
for i in range(1, N+1):
p.append(list(map(int, sys.stdin.readline().split())))
d[i] = p[i]
d[i][0] = min(d[i - 1][1], d[i - 1][2]) + p[i][0]
d[i][1] = min(d[i - 1][0], d[i - 1][2]) + p[i][1]
d[i][2] = min(d[i - 1][0], d[i - 1][1]) + p[i][2]
print(min(d[N]))'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 11057 - 오르막 수 [파이썬] (0) | 2022.04.22 |
|---|---|
| 백준 1309 - 동물원 [파이썬] (0) | 2022.04.22 |
| 백준 15988 - 1, 2, 3 더하기 3 [파이썬] (0) | 2022.04.21 |
| 백준 1699 - 제곱수의 합 [파이썬] (0) | 2022.04.21 |
| 백준 1912 - 연속합 [파이썬] (0) | 2022.04.20 |