5. DP
[DP] 백준 1149번 - RGB 거리
asdklfjlasdlfkj
2020. 1. 8. 19:29
https://www.acmicpc.net/problem/1149
1149번: RGB거리
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.
www.acmicpc.net
백준 DP 연습문제다.
입력받은 각 위치의 RGB값을 갖고 이전에 합산해둔 (메모이제이션) 최소 RGB 비용을 비교해 더 작은 비용값에 더해주며 최종 N의 자리까지 가면된다. N의 자리까지 가면 세 색깔에 대한 값을 모두 비교해주어 그 중 가장 작은 값을 답으로 출력하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <iostream>
#include <algorithm>
#define maxlen 1001
using namespace std;
int DP[maxlen][3];
int N;
int main(){
cin >> N;
DP[0][0] = DP[0][1] = DP[0][2] = 0;
for (int i = 1; i <= N; i++){
for (int j = 0; j < 3; j++){
cin >> DP[i][j];
}
DP[i][0] += min(DP[i - 1][1], DP[i - 1][2]);
DP[i][1] += min(DP[i - 1][0], DP[i - 1][2]);
DP[i][2] += min(DP[i - 1][0], DP[i - 1][1]);
}
cout << min(DP[N][0], min(DP[N][1], DP[N][2]));
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |