[1149번] RGB거리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식

앞이 어떻게 됐건 신경쓰지말고 i번째라고 생각해보자.

i번째 집에 r이 칠해질 때 최소 비용(DP[i][0])은 i-1번째 집에 g가 칠해져있을 때 혹은 b가 칠해져있을 때 가능하다.

i번째 집에 g가 칠해질 때 최소 비용(DP[i][1])은 i-1번째 집에 r이 칠해져있을 때 혹은 b가 칠해져있을 때 가능하다.

i번째 집에 b가 칠해질 때 최소 비용(DP[i][2])은 i-1번째 집에 r이 칠해져있을 때 혹은 g가 칠해져있을 때 가능하다.

    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];

    }

이 코드를 통해 모든 이웃간에 중복없이 집에 색칠이 조건에 맞게 칠해진다.

소스 코드 : 

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

#include <iostream> #include <cstdio>   #define min(a,b)(a < b ? a : b)   using namespace std;   long long int cost[1001][3]; long long int DP[1001][3];   int main() {     int n;     long long int r, g, b;          scanf("%d", &n);       for (int i = 0; i < n; i++)     {         scanf("%lld %lld %lld", &r, &g, &b);           cost[i][0] = r;         cost[i][1] = g;         cost[i][2] = b;     }       DP[0][0] = cost[0][0];     DP[0][1] = cost[0][1];     DP[0][2] = cost[0][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("%lld", min(min(DP[n - 1][0], DP[n - 1][1]), DP[n - 1][2]));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus