RGB거리
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (언어별 추가 시간 없음) | 128 MB | 28508 | 12672 | 9483 | 46.252% |
문제
RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다.
각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.
예제 입력 1
1
2
3
4
3
26 40 83
49 60 57
13 89 99
예제 출력 1
1
96
풀이
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
#include <iostream>
#include <vector>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main(){
IOFAST();
int i,j,n;
cin >> n;
vector<vector<int>> v,dp;
v.resize(n); dp.resize(n);
for(i=0;i<n;i++){
for(j=0;j<3;j++){
int temp;
cin >> temp;
v[i].push_back(temp);
dp[i].push_back(0);
}
}
dp[0][0] =v[0][0]; dp[0][1]=v[0][1]; dp[0][2]=v[0][2];
for(i=1;i<n;i++){
dp[i][0]=min(dp[i-1][1],dp[i-1][2])+v[i][0];
dp[i][1]=min(dp[i-1][0],dp[i-1][2])+v[i][1];
dp[i][2]=min(dp[i-1][0],dp[i-1][1])+v[i][2];
}
int minNum= min(min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
cout << minNum << '\n';
}