[백준 / BOJ] - 1149번 RGB거리 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [1149] 

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

문제

 

 

 

풀이

 

동적 계획법의 기본은 큰 문제를 작은 문제로 쪼개는 것이다.

이번 문제를 작은 단위로 쪼개보면,

i번째 집을 빨강, 초록, 파랑으로 칠했을 때의 비용의 최소값을 구해 나가는 것이다.

 

이를 구하고 저장하기 위한 배열 house[1001][3]을 선언한다.

house[i][0] 에는 i번째 집을 빨강색으로 칠할 때의 최소비용,

house[i][1] 에는 i번째 집을 초록색으로 칠할 때의 최소비용,

house[i][2] 에는 i번째 집을 파란색으로 칠할 때의 최소비용을 저장한다.

 

house[i]가 빨강색으로 칠해지기 위해서는 이전 집이 초록색이거나 파란색이어야하고,

파란색으로 칠해지기 위해서는 이전 집이 빨강색이거나 초록색이어야하고,

초록색으로 칠해지기 위해서는 이전 집이 빨강색이거나 파란색이어야한다.

 

따라서 이를 반복문으로 구현하면, 다음과 같다.

 

    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];
    }

 

 

코드

 

#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]));
}

 

 

평가

 

큰 문제를 작은 단위의 문제로 쪼개고,

작은 문제들의 결과값을 배열에 저장하여 사용하는 방법을 배우고 넘어가면 좋을 듯한 문제이다.