백준 1149 RGB거리 C++

문제

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

1149번: RGB거리

 

코드

#include <bits/stdc++.h>

using namespace std;

int n, cost[3], house[1004][3];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);                                                                                                                                                                 
    
    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]));

    return 0;
}

 

 

house[i][color] 는 i번째 집을 빨강 / 초록 / 파랑으로 칠했을 때의 최소비용을 의미한다.

즉,  house[i][0] 는 i번째 집을 빨강으로칠했을 때의 최소비용을 의미한다.

       house[i][1] 는 i번째 집을 초록으로칠했을 때의 최소비용을 의미한다.

       house[i][2] 는 i번째 집을 파랑으로칠했을 때의 최소비용을 의미한다.

 

위 코드를 찍어보면 아래와 같이 나오는 것을 알 수 있다.

house[1][0] 은 1번째 집을 빨강으로 칠했을 때의 최소비용으로, 이전 집이 없기 때문에 이전집의 값은 모두 0으로 초기화 되어있는 상태이다. 1번째 집을 빨강으로 칠했을 때의 비용을 더해서 house[1][0] 값을 갱신한다.

house[1][1] 은 1번째 집을 초록으로 칠했을 때의 최소비용으로, 이전 집이 없기 때문에 이전집의 값은 모두 0으로 초기화 되어있는 상태이다. 1번째 집을 초록으로 칠했을 때의 비용을 더해서 house[1][1] 값을 갱신한다.

house[1][2] 은 1번째 집을 파랑으로 칠했을 때의 최소비용으로, 이전 집이 없기 때문에 이전집의 값은 모두 0으로 초기화 되어있는 상태이다. 1번째 집을 파랑으로 칠했을 때의 비용을 더해서 house[1][2] 값을 갱신한다.

 

house[2][0] 은 2번째 집을 빨강으로 칠했을 때의 최소비용으로, 1번째 집을 초록또는 파랑으로 칠했을 때의 최소비용을 구한다음, 2번째 집을 빨강으로 칠했을 때의 비용을 더해서 house[2][0] 값을 갱신한다.

house[2][1] 은 2번째 집을 초록으로 칠했을 때의 최소비용으로, 1번째 집을 빨강또는 파랑으로 칠했을 때의 최소비용을 구한다음, 2번째 집을 초록으로 칠했을 때의 비용을 더해서 house[2][1] 값을 갱신한다.

house[2][2] 은 2번째 집을 파랑으로 칠했을 때의 최소비용으로, 1번째 집을 초록또는 빨강으로 칠했을 때의 최소비용을 구한다음, 2번째 집을 초록으로 칠했을 때의 비용을 더해서 house[2][2] 값을 갱신한다.

 

house[3][0] 은 3번째 집을 빨강으로 칠했을 때의 최소비용으로, 2번째 집을 초록또는 파랑으로 칠했을 때의 최소비용을 구한다음, 3번째 집을 빨강으로 칠했을 때의 비용을 더해서 house[3][0] 값을 갱신한다.

house[3][1] 은 3번째 집을 초록으로 칠했을 때의 최소비용으로, 2번째 집을 빨강또는 파랑으로 칠했을 때의 최소비용을 구한다음, 3번째 집을 초록으로 칠했을 때의 비용을 더해서 house[3][1] 값을 갱신한다.

house[3][2] 은 3번째 집을 파랑으로 칠했을 때의 최소비용으로, 2번째 집을 초록또는 빨강으로 칠했을 때의 최소비용을 구한다음, 3번째 집을 초록으로 칠했을 때의 비용을 더해서 house[3][2] 값을 갱신한다.

 

그런다음 house[3][0], house[3][1], house[3][2] 중에서 가장 작은 값을 구하면 문제에서 요구하는 값을 출력할 수 있다.

여기서 마직막집에 대한 배열값만 비교를해도 되는 이유는,

house[3][0] 는 3번째 집을 빨강색으로 칠했을 경우 비용을 의미하고

house[3][1] 는 3번째 집을 초록색으로 칠했을 경우 비용을 의미하고

house[3][2] 는 3번째 집을 파랑색으로 칠했을 경우 비용을 의미하는데,

 

더 자세히 풀어서 설명하면,

house[3][0] 는 3번째 집을 빨강색으로 칠했을 경우에는, 2번째 집을 초록색 또는 파랑색으로 칠했을 경우의 최소값이 담겨있고, 1번째 2번째 집과 겹치지 않는 색으로 칠했을 경우의 최소값이 담겨있기 때문에 house[3][0] 를 출력하면 1번째, 2번째, 3번째 집을 모두 칠한 비용이 담겨져있음을 의미한다. 

house[3][1] 는 3번째 집을 초록색으로 칠했을 경우에는, 2번째 집을 빨강색 또는 파랑색 으로 칠했을 경우의 최소값이 담겨있고, 1번째 2번째 집과 겹치지 않는 색으로 칠했을 경우의 최소값이 담겨있기 때문에 house[3][1] 를 출력하면 1번째, 2번째, 3번째 집을 모두 칠한 비용이 담겨져있음을 의미한다. 

house[3][2] 는 3번째 집을 파랑색으로 칠했을 경우에는, 2번째 집을 빨강색 또는 초록색으로 칠했을 경우의 최소값이 담겨있고, 1번째 2번째 집과 겹치지 않는 색으로 칠했을 경우의 최소값이 담겨있기 때문에 house[3][1] 를 출력하면 1번째, 2번째, 3번째 집을 모두 칠한 비용이 담겨져있음을 의미한다.