[백준] 1149번 : RGB거리

문제

 

---

풀이

 

이걸 이렇게 표현하는게 맞나? 싶지만 동적계획법 문제를 풀 때는 i번째가 ~라면 i-1번째는 뭐였을까? 라는 방법으로 접근하는 것이 좋다.

보통 문제를 풀 때 0번째가 이거라면 1번째는 이게 되고 2번째는...식으로 생각하기 마련인데 동적계획법은 반대 방향으로 가야한다.

 

이 문제도 마찬가지이다. 첫번째 두번째 집이 무슨 색인지는 궁금하지 않고, i번째 집을 빨간색으로 칠한다고 생각해보자.

i번째 집이 빨간색이라면 i-1번째 집은 파란색(1번 경우)이나 초록색(2번 경우)일 것이다.

그렇다면 i번째 집을 빨간색으로 칠할 때의 최솟값은? 1번 경우와 2번 경우 중 더 작은 값을 택하면 될 것이다.

---

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;

int house[1000][3];

int coloring(int num) {
    for (int i = 1; i < num; i++) {
        //i번째 집을 R로 칠할 때 i-1번째 집은 G나 B일 것임. 그 이전 집이 G인 경우와 B인 경우 중 더 작은 것과 i번째 집의 R을 더하면 됨
        house[i][0] += min(house[i - 1][1], house[i - 1][2]); //R로 색칠
        house[i][1] += min(house[i - 1][0], house[i - 1][2]); //G로 색칠
        house[i][2] += min(house[i - 1][1], house[i - 1][0]); //B로 색칠
    }
    return min(min(house[num - 1][0], house[num - 1][1]), house[num - 1][2]); //RGB중 가장 작은 애가 최소값임
}

int main() {
    int N;

    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 3; j++)
            cin >> house[i][j];
    }
    cout << coloring(N);
}

초기 입력은 하나하나의 집을 RGB로 칠하는 각각의 비용을 담고있다.

coloring함수를 통해 이 입력을 각 집을 RGB로 칠하기 위해 드는 총 비용으로 갱신해 나가는 것이다.