백준 #1149 RGB 거리

이번 문제는 일렬로 늘어선 집들이 있을 때, 여기에 빨강, 초록, 파랑색으로 집을 색칠하는 것입니다.  색마다 칠하는 비용이 집마다 주어지고, 이웃간에는 색을 달리 칠해야 합니다.  최소의 비용으로 칠을 할 때, 그 비용은 얼마인 가입니다.

 

RGB Street

문제의 난이도는 Silver I 문제입니다.  정답률도 47.2%로 적당한 수준의 문제입니다.  기초적인 알고리즘 지식만 있으면 풀 수 있는 문제입니다.

 

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

1149번: RGB거리

 

이 문제는 동적 프로그래밍을 이용하면 됩니다.  k번째 집에 색을 칠하는 비용을 \(C_{Rk}\), \(C_{Gk}\), \(C_{Bk}\) 라고 하고, k번째 집에 R, G, B로 칠할 때의 최소값을 \(dp_R(k)\), \(dp_G(k)\), \(dp_B(k)\) 라고 한다면,

\(dp_R(0) = dp_G(0) = dp_B(0) = 0\)

\(dp_R(k) = min( dp_G(k-1), dp_B(k-1)) + C_{Rk} )\)

\(dp_G(k) = min( dp_R(k-1), dp_B(k-1)) + C_{Gk} )\)

\(dp_B(k) = min( dp_R(k-1), dp_G(k-1)) + C_{Bk} )\)

로 놓을 수 있습니다.

이래서 최종적으로 \(min(dp_R(n), dp_G(n), dp_B(n))\) 값을 출력으로 내주면 됩니다.

 

이 알고리즘으로 제가 작성한 소스코드입니다.  소스코드는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1149 - RGB Street
//    - by Aubrey Choi
//    - created at 2019-06-02
//--------------------------------------------------------------------
#include <stdio.h>

int min(int a, int b) { return a < b ? a : b; }
int min(int a, int b, int c)
{
  int min = a;
  if(b < min) min = b;
  if(c < min) min = c;
  return min;
}
int main()
{
  int n, r, g, b;
  int dp[1000][3];
  scanf("%d", &n);
  scanf("%d%d%d", dp[0], dp[0] + 1, dp[0] + 2);
  for(int i = 1; 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;
  }
  printf("%d\n", min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]));
}