[백준 C++] 17404번 RGB거리 2

17404번: RGB거리 2

문제 요약

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
• 출력: 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다. ``` 예제1

입력 3 26 40 83 49 60 57 13 89 99 출력 110

## 풀이
RGB거리와 크게 다르지 않다. dp로 r, g, b로 시작하는 경우 각각을 구해서 마지막에 초기값과 다른 집의 색만 min에 넣는다. 이를 위해 초기에 초기값이 아닌 집에는 큰 값을 넣어 dp에 벗어나게 만들고 마지막에는 초기값과 다를때만 min에 넣는식으로 동작하면 된다.

## 어려웠던 점
rgb를 괜히 구조체로 만들려다가 고생했다. 그냥 하던데로 하자. 

## 배운 점 / 느낀 점
RGB와 크게 다르지 않은 문제였지만 초기값을 고정하여 3번 돌린다는 아이디어가 생각보다 오래걸려서 나왔다. dp를 더 공부하자.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;



int n, ans;
int a[1005][3];
int dp[1005][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    ans = 1000*10000;
    for(int i = 0; i < n; i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    for(int i = 0; i < 3; i++){
        for (int j = 0; j < 3; j++) {
            if(j == i){
                dp[0][j] = a[0][j];
            }
            else{
                dp[0][j] = 2000;
            }
        }
        for (int j = 1; j < n; j++) {
            dp[j][0] = a[j][0] + min(dp[j-1][1], dp[j-1][2]);
            dp[j][1] = a[j][1] + min(dp[j-1][0], dp[j-1][2]);
            dp[j][2] = a[j][2] + min(dp[j-1][0], dp[j-1][1]);
        }
        for (int j = 0; j < 3; j++) {
            if(j!=i){
                ans = min(ans, dp[n-1][j]);
            }
        }
        
    }
    cout << ans;
    

    return 0;
}