[백준 BOJ][DP] 1149 RGB거리

1149_RGB거리

링크

https://www.acmicpc.net/problem/1149

 

풀이

 

집 i의 이웃은 집 i-1과 i+1이고, 이웃은 같은 색으로 칠할 수 없습니다.

 

DP[i][j] (집 i를 j색으로 칠했을 때까지의 최소 비용, j = 0 R, 1 G, 2 B)

cost[i][j] (집 i를 j색으로 칠할 때의 비용, j = 0 R, 1 G, 2 B) 이라고 정의하겠습니다.

 

그렇다면 DP[i][0]은 이웃은 같은 색을 칠할 수 없다는 조건에 의해,

min(DP[i-1][1], DP[i-1][2]) + cost[i][0]로 정의됩니다. (전에 다른 색 G, B로 칠했을 때까지의 최소 비용 + 현재 R로 칠했을 때의 비용)

 

즉, 나머지 색들도 생각해보면 다음과 같은 식이 나옵니다.

 

DP[i][0] = min(DP[i-1][1], DP[i-1][2]) + cost[i][0]

DP[i][1] = min(DP[i - 1][0], DP[i - 1][2]) + cost[i][1]

DP[i][2] = min(DP[i - 1][0], DP[i - 1][1]) + cost[i][2];

 

마지막에 DP[n][0], DP[n][1], DP[n][2] 중 최솟값을 출력해주면 됩니다.

 

 

코드

 

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

//1149_RGB거리 #include <cstdio> #include <algorithm> using namespace std;   int DP[1001][3]; //0 R, 1 G, 2 B                 //n번째 집을 m 색깔로 칠했을 때의 min cost int cost[1001][3];   int main() {     int n;       scanf("%d", &n);          for (int i = 1; i <= n; ++i) scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);          for (int i = 1; i <= n; ++i) {         DP[i][0] = min(DP[i - 1][1], DP[i - 1][2]) + cost[i][0];         DP[i][1] = min(DP[i - 1][0], DP[i - 1][2]) + cost[i][1];         DP[i][2] = min(DP[i - 1][0], DP[i - 1][1]) + cost[i][2];     }       printf("%d\n", min(min(DP[n][0], DP[n][1]), DP[n][2]));          return 0; } Colored by Color Scripter

cs