[BOJ/C++] RGB거리(1149번)

1. 개요

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

1149번: RGB거리

1-1. 설명

RGB 거리에는 집이 N개 존재한다. 거리는 선분으로 나타낼 수 있으며, 1번부터 N번 집이 순서대로 있다. 집은 빨강,초록,파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 RGB로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하며 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성한다.

 - 1번 집 색은 2번집 색과 일치 X

 - N번 집 색은 N-1번 집 색과 일치 X

 - i(2<=i<=N-1)번 집 색은 i-1, i+1번 집색과 일치 X

1-2. 제한 사항

 - 첫 줄에 집의 수 N이 주어지며, N은 2 이상 1,000 이하

 - 둘째 줄부터 N개 줄에는 각집을 RGB로 칠하는 비용이 1번집부터 한줄에 하나씩 주어지며, 비용은 1,000 이하 자연수

---

2. 구현

2-1. 풀이

다이나믹 프로그래밍을 이용하여 Bottom-up 방식으로, 반복문을 이용해 하나씩 채워나가면 된다. 점화식은 그렇게 복잡하지 않다.

2-2. 코드 

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001][3];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    int N, r, g, b;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        cin >> r >> g >> b;
        if (i == 1) {
            dp[i][0] = r;
            dp[i][1] = g;
            dp[i][2] = b;
            continue;
        }

        // 각 RGB의 점화식
        dp[i][0] = min(dp[i - 1][1] + r, dp[i - 1][2] + r);
        dp[i][1] = min(dp[i - 1][0] + g, dp[i - 1][2] + g);
        dp[i][2] = min(dp[i - 1][0] + b, dp[i - 1][1] + b);
        // --- 
    }
    auto result = *min_element(dp[N], dp[N] + 3);
    cout << result << "\n";
    return 0;
}