[백준 1149번] RGB 거리 풀이

1149번: RGB거리

 

집 N개를 각각 빨강(r), 초록(g), 파랑(b)으로 칠할 때의 비용이 주어진다.

i번째 집은 i-1 번째 집과 다른 색으로 칠해져야 한다.

 

N개의 집에 대하여 칠할 수 있는 모든 조합을 탐색하면,

 

//R로 시작하는 경우

      R
     /
    G
   / \
  /   B
R          ... 
  \   R
   \ / 
    B
     \
      G

 

경우의 수가 2의 거듭제곱으로 늘어 시간 복잡도는 3 * 2^(N-1) 이 된다. 해당 방법은 시간 초과가 예상되므로, 다이내믹 프로그래밍(dp) 점화식을 세워 문제를 해결해보고자 한다.

 

i번째 집의 경우, r로 칠해지거나 g로 칠해지거나 b로 칠해질 수 있다. 각 경우에 대하여 최소 비용을 구하기 위하여, 다음과 같이 정의한다.

 

dp[i][0] = i번째 집이 r로 칠해질 때 i번째 집까지의 최소 비용

dp[i][1] = i번째 집이 g로 칠해질 때 i번째 집까지의 최소 비용

dp[i][2] = i번째 집이 b로 칠해질 때 i번째 집까지의 최소 비용

 

i번째 집이 r로 칠해질 경우, 이전 집인 i-1번째 집은 g 혹은 b로만 칠해질 수 있다. 따라서 다음이 성립한다.

 

// dp[i][0]: i번째 집을 0(red)로 칠할 때 i번째 집까지 칠하는 최소비용
// dp[i-1][1]: i-1번째 집을 1(green)로 칠할 때 i-1번째 집까지 칠하는 최소비용
// dp[i-1][2]: i-1번째 집을 2(blue)로 칠할 때 i-1번째 집까지 칠하는 최소비용
// r: i번째 집을 red로 칠할 때 비용

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + r;

 

이와 마찬가지로, i번째 집이 g나 b로 칠해질 경우에도 가능한 이전 집의 색깔에 따라 다음과 같이 표현할 수 있다.

 

// dp[i][1]: i번째 집을 1(green)으로 칠할 때 i번째 집까지 칠하는 최소비용
// dp[i][2]: i번째 집을 2(blue)로 칠할 때 i번째 집까지 칠하는 최소비용
// g: i번째 집을 green으로 칠할 때 비용
// b: i번째 집을 blue로 칠할 때 비용

dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + g;
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + b;

 

i=N까지 반복하여 dp[N][0], dp[N][1], dp[N][2]를 각각 구한 뒤, 이들 중 최솟값을 구하면 N번째 집까지 칠할 때의 최소비용이 도출된다.

 

int re = 1001*N;
for (int i=0; i<=2; i++) re = min(re, dp[N][i]);
printf("%d", re);

 

전체 코드는 다음과 같다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
#include <queue>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

int dp[1001][3];

int main() {

    int N, r, g, b;
    scanf("%d %d %d %d", &N, &r, &g, &b);
    dp[1][0] = r, dp[1][1] = g, dp[1][2] = b;

    for (int i=2; i<=N; i++) {
        scanf("%d %d %d", &r, &g, &b);
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + r;
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + g;
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + b;
    }

    int re = 1001*N;
    for (int i=0; i<=2; i++) re = min(re, dp[N][i]);
    printf("%d", re);
    return 0;
}