<백준>1149번 RGB거리

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

문제

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

문제 해결 과정:

-이차원 배열을 만들고 행 자리에는 R,G,B를 각각 0,1,2로 표현

-열 자리에는 집들의 집합이다.

-이웃은 같은 색으로 칠할 수 없으므로 각 행 마다 자신을 제외한 다른 행의 가격중 작은 값을 전값에 더한다

-이렇게 점화식을 표현 Rn = r + Rn-1 로 나타낼 수 있다.

-마지막으로 각 행들 중 최솟값을 구한다. 

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int main() {
 
    int N;
    cin >> N;
    int r, g, b;
    int RGB[3][1001];
 
    scanf_s("%d %d %d", &r, &g, &b);
    RGB[0][0] = r;
    RGB[1][0] = g;
    RGB[2][0] = b;
 
 
    for (int i = 1; i < N; i++) {
        scanf_s("%d %d %d",&r,&g,&b);
 
        RGB[0][i] = r + min(RGB[1][i-1], RGB[2][i-1]);
        RGB[1][i] = g + min(RGB[2][i-1], RGB[0][i-1]);
        RGB[2][i] = b + min(RGB[0][i-1], RGB[1][i-1]);
    }
 
    int result = min(RGB[0][N - 1], RGB[1][N - 1]);
    result = min(result, RGB[2][N - 1]);
 
    cout << result<<endl;
    return 0;
}