[백준 / BOJ] C++ 1149 RGB거리

1149번: RGB거리

 

문제

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

1149번: RGB거리

 

 

풀이

칠해야 하는 집의 수 N이 주어진다. 이후 각 집에 대하여 빨강, 초록, 파랑으로 칠했을 때의 비용이 한 줄에 주어진다. i번째 집의 색은 i-1, i+1번째 집의 색과는 달라야 한다. 조건에 맞게 모든 집을 칠했을 때 비용의 최솟값을 구하는 문제다.

 

dp를 사용해 풀 수 있다. dp[1001][3] 크기의 0으로 초기화된 이중 배열을 만든다. 1001은 몇 번째 집인지를 의미하고 3은 R, G, B 중 하나로 칠했을 각각의 경우의 가격을 의미한다. i번째 집의 비용이 입력될 때, 빨간색을 칠할 경우엔 i-1번째 집에 초록색, 파란색을 칠한 경우 중 최솟값에 더한 값을 저장한다. 파란색인 경우엔 빨간색, 초록색 중 최솟값, 초록색인 경우엔 빨간색, 파란색 중 최솟값에 가격을 더한다.

 

마지막 집까지 색칠한 후, 마지막 집에 칠한 색깔이 빨간색, 초록색, 파란색인 각 경우에 대하여 최솟값을 출력하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  int dp[1001][3] = {0};
  for (int i = 1; i <= n; i++) {
    int r, g, b;
    cin >> 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;
  }
  cout << min(min(dp[n][0], dp[n][1]), dp[n][2]) << '\n';
  return 0;
}