백준 #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로 칠할 때의 최소값을 $d{p}_R(k)$, $d{p}_G(k)$, $d{p}_B(k)$ 라고 한다면,

$d{p}_R(0)=d{p}_G(0)=d{p}_B(0)=0$

$d{p}_R(k)=min(d{p}_G(k-1),d{p}_B(k-1))+C_{Rk})$

$d{p}_G(k)=min(d{p}_R(k-1),d{p}_B(k-1))+C_{Gk})$

$d{p}_B(k)=min(d{p}_R(k-1),d{p}_G(k-1))+C_{Bk})$

로 놓을 수 있습니다.

이래서 최종적으로 $min(d{p}_R(n),d{p}_G(n),d{p}_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]));
}