본문 바로가기

컴퓨터/Online Judge

[acmicpc.net] 1149 RGB거리

반응형

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


문제 내용


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


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


소스코드


#include <iostream>
using namespace std;
 
int main() {
    int **last = new int*[3];
    int **val = new int*[3];
    int N;
    cin >> N;
    for(int i=0; i<3; i++){
        last[i] = new int[N];
        val[i] = new int[N];
    }
    for(int i=0; i<N; i++){
        for(int j=0; j<3; j++){
            cin >> val[j][i];
        }
    }
    last[0][0] = val[0][0];
    last[1][0] = val[1][0];
    last[2][0] = val[2][0];
    for(int i=1; i<N; i++){
        last[0][i] = min(last[1][i-1], last[2][i-1])+val[0][i];
        last[1][i] = min(last[0][i-1], last[2][i-1])+val[1][i];
        last[2][i] = min(last[1][i-1], last[0][i-1])+val[2][i];
    }
    cout << min(min(last[0][N-1], last[1][N-1]), last[2][N-1]);
    return 0;
}



반응형