(C++) 백준 1149번 - RGB 거리

문제 링크 : https://www.acmicpc.net/problem/1149

1149번: RGB거리

풀이

다이나믹 프로그래밍을 이용하여 풀이하였다.

2차원 배열을 사용해서 house[x][0]은 x번째 집이 빨간색일 때의 최소 비용, house[x][1]은 x번째 집이 초록색일 때의 최소 비용, house[x][2]은 x번째 집이 파란색일 때의 최소 비용을 저장하도록 하였다. 

#include <iostream>
#include <algorithm>

using namespace std;

int house[1002][5];
int v[1002][5];
int n;

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

    cin >> n;
    for(int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1] >> v[i][2];
    house[0][0] = v[0][0];
    house[0][1] = v[0][1];
    house[0][2] = v[0][2];

    for(int i = 1; i < n; i++){
        house[i][0] = min(house[i-1][1], house[i-1][2]) + v[i][0];
        house[i][1] = min(house[i-1][0], house[i-1][2]) + v[i][1];
        house[i][2] = min(house[i-1][0], house[i-1][1]) + v[i][2];
    }
    cout << min({house[n-1][0], house[n-1][1], house[n-1][2]});
}