[C++] 백준 1149 RGB거리

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() 
{
    int n;
    cin >> n;
    vector<int> house(3, 0);

    for (int i = 0; i < n; i++) 
    {
        int color[3];
        int result[3];
        cin >> color[0] >> color[1] >> color[2];

        result[0] = min(house[1] + color[0], house[2] + color[0]);
        result[1] = min(house[0] + color[1], house[2] + color[1]);
        result[2] = min(house[0] + color[2], house[1] + color[2]);

        house[0] = result[0];
        house[1] = result[1];
        house[2] = result[2];
    }

    cout << min({ house[0], house[1], house[2] });

    return 0;
}

 

문제의 단서

- N만큼의 집

- 빨강, 초록, 파랑의 3가지색

- 색에 대한 정보를 합쳤을 때 색마다 -+1에 있는 집과 색이 달라야한다.

 

풀이

1. 3개의 색깔과 색깔 * n만큼의 색깔 칠하기 입력이 이뤄진다. 여기서 경우의 수를 따져본다.

1번째 줄

A / B / C

2번째 줄

(B,C) A / (A,C) B / (A,B) C

3번째 줄

A : (A,C), B / ((A,B), C

B : (B,C) A / (A,B) C

C : (A,C), B / (B,C) A

 

2. 점화식을 세워보자

A는 C와 B에 적립된 값중 작은 값,

B는 A와 C에 적립된 값중 작은 값,

C는 A와 B에 적립된 값중 작은 값을 불러오는 걸 확인할 수가 있다.

 

3. 최종적으로 3가지의 적립된 값중에 작은 값을 출력하면 된다.

 

느낀점

빠르게 규칙을 찾는 것이 dp를 빠르게 해결하는 방법인 것같다. 그 과정을 빠르게 찾는 방법은 그냥 모든 경우의 수를 경우에 따라 3~5번째 정도까지 직접 해보면 규칙성이 나타난다. 더 어려운 문제에서는 다를 수도 있겠다.

 

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