[Silver 1] 1149번 RGB거리

 

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

1149번: RGB거리

 

이 문제는 Dynamic Programming을 사용해서 해결할 수 있다.

 

주요 알고리즘은 다음과 같다.

1. N개의 집에 대해 RGB의 비용을 입력받는다.
2. 이때 1번째 집은 0번째 집. 즉, 0과 비교하여 R G B의 최소 값을 house 배열에 저장한다.
   • R G B의 최소 값을 구할 때 R의 경우 이전 값의 G와 B의 최소 값과 더한다. (인접한 경우 같은 색을 칠하면 안된다)
3. N번째 집은 이전에 구한 R G B의 최소 값을 저장한다. 
4. 입력이 끝나면 house배열의 N번째 값의 R G B 인덱스에는 각각의 경로의 최소 값이 더해져 있다.
5. R G B의 최소 값 중 최소 값을 찾아서 출력하면 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int house[1001][3];
int main() {
    int N;
    int cost[3];
    house[0][0] = 0;
    house[0][1] = 0;
    house[0][2] = 0;
    cin >> N;
    for(int i = 1; i <= N; ++i)
    {
        cin >> cost[0] >> cost[1] >> cost[2];
        house[i][0] = min(house[i-1][1],house[i-1][2]) + cost[0];
        house[i][1] = min(house[i-1][0],house[i-1][2]) + cost[1];
        house[i][2] = min(house[i-1][1],house[i-1][0]) + cost[2];
    }
    cout << min(house[N][2],min(house[N][0],house[N][1]));
}