문제
풀이
dp를 활용한 문제로, 조건이 길게 적혀있긴 하지만, 다음의 도시는 이전 도시와 색깔이 같지 않게끔, 그리고 첫번째와 마지막 도시의 색깔이 같지 않으면 되는 문제이다. 첫번째 도시를 가장 바깥 loop에서 정해주고, N-1번째 도시까지 각각 그 전 최소값에 R, G, B 색상을 칠했을 때의 경우를 다 구한다. 그 이후 최솟값을 마지막과 첫번째 색깔이 같지 않은 경우만 tracking하여 정답을 구한다.
소스 코드
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
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#define INF 987654321;
using namespace std;
int main(){
int N;
scanf("%d", &N);
int cost[1001][3]; // i번째 집의 R, G, B로 각각 칠했을 때 드는 비용
for(int i = 0 ; i<N; i++){
scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);
}
//집은 0~N-1번까지 존재
int dp[1001][3];
int result = INF;
for(int i = 0; i<3; i++){ // 0번째 집이 R, G, B인지 확인
for(int j = 0; j<3; j++){
if(i==j){ //
dp[0][j] = cost[0][j]; // i색깔로 칠하는 비용
}
else{ // 다르다면...
dp[0][j] = INF; // 다르다면 예외 처리
}
}
for(int j = 1; j<N; j++){
dp[j][0] = min(dp[j-1][1], dp[j-1][2]) + cost[j][0];
dp[j][1] = min(dp[j-1][0], dp[j-1][2]) + cost[j][1];
dp[j][2] = min(dp[j-1][0], dp[j-1][1]) + cost[j][2];
}
for(int j = 0; j<3; j++){
if(i==j){ // 첫번째와 N-1번째 색깔이 같다면...
continue; // 무시
}
else{ // 첫번째와 N-1번째 색갈이 다르다면...
result = min(result, dp[N-1][j]); // N-1번째를 0번째 집과 다른 색깔로 칠했을 때의 최소비용
}
}
}
printf("%d\n", result);
}
