백준 알고리즘 기초/다이내믹 프로그래밍
[백준][DP] RGB거리2
코딩고치
2020. 3. 31. 22:45
1. 문제 주소
https://www.acmicpc.net/problem/17404
17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
www.acmicpc.net
2. 문제
이전에 풀었던 RGB거리에서 첫 번째 집의 색과 N번째 집의 색이 달라야 한다는 조건이 추가된 문제이다. 이 조건을 추가하여 최솟값을 구하면 된다.
3. 소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#include <algorithm>
using namespace std;
int total_price[1001][3];
int color_price[1001][3];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++) {
cin >> color_price[i][j];
}
}
int result = 1000 * 1001;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i == j) {
total_price[1][j] = color_price[1][j];
}
else {
total_price[1][j] = 1000 * 1001;
}
}
for (int k = 2; k <= n; k++) {
total_price[k][0] = min(total_price[k - 1][1], total_price[k - 1][2]) + color_price[k][0];
total_price[k][1] = min(total_price[k - 1][0], total_price[k - 1][2]) + color_price[k][1];
total_price[k][2] = min(total_price[k - 1][0], total_price[k - 1][1]) + color_price[k][2];
}
for (int j = 0; j < 3; j++) {
if(i != j)
result = min(result, total_price[n][j]);
}
}
cout << result << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|