(C++) 백준 1149번

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

용꿀 2023. 5. 7. 16:24

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

1149번: RGB거리

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나

www.acmicpc.net

풀이

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

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]});
}