백준 1149 RGB거리 c++ [컴공과고씨]

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

1149번: RGB거리

 

문제 정리

집을 3가지 색으로 칠할 수 있음.

각 집마다 각 색으로 칠하는 비용이 다름.

각 집의 색깔은 바로 앞 집과 바로 다음 집의 색깔과 같으면 안됨.

비용을 최소로 칠하는 비용은?

 

문제 해결 방법

이 문제의 경우 다이나믹 프로그래밍을 이용하면 쉽게 풀 수 있다.

일단 dp[3][n]이라는 배열을 만든다.

이 배열의 의미를 먼저 알아보자.

앞에 3이라는 것은 3가지 색깔을 말하고 n은 집을 말한다.

그럼 한 집당 3가지 색깔을 칠 할 수 있다. 

그래서 dp[1][1]이 뜻하는 바는 1번째 색깔로 1번째 집을 칠한 것을 말한다.

dp[0][1]은 0번째 색깔로 1번째 집을 칠한 것을 말합니다.

그렇다면  3번째 집을 0번 색으로 칠하기 위한 조건은 뭐냐?

바로 2번째 집에서 1번으로 칠한 값, 2번으로 칠한 값 중 최소값을 골라주면 된다.

3번째 집을 1번 색으로 칠하기 위한 조건은?

쉽게 2번째 집에서 0번, 2번으로 칠한 값 중 최소를 골라주면 되는 것이다.

그래서 우리가 구하고자 하는 집의 최소 비용은

dp[0][j] = min(dp[1][j-1], dp[2][j-1]) + 현재 집을 0번 색으로 칠하는 비용 : j집을 0번 색으로 칠할 때 최소 비용

dp[1][j] = min(dp[0][j-1], dp[2][j-1]) + 현재 집을 0번 색으로 칠하는 비용 : j집을 0번 색으로 칠할 때 최소 비용

dp[2][j] = min(dp[0][j-1], dp[1][j-1]) + 현재 집을 0번 색으로 칠하는 비용 : j집을 0번 색으로 칠할 때 최소 비용

 

이런 식으로 나아가면 현재 집 기준 앞 뒤 모두 다르게 색을 칠하면서 최소 비용을 얻을 수 있다.

 

전체 코드

#include <iostream>
using namespace std;
int minum(int a, int b){
    if(a>b)
        return b;
    else
        return a;
}
int main(){
    int n;
    int dp[3][1003]; // i번 색으로 j번 집을 칠하는데 드는 최소 비용 저장
    int rgb[3][1003]; // 집을 칠하는데 드는 비용
    cin >> n;
    for (int i = 0; i < n;i++){ 
        cin >> rgb[0][i] >> rgb[1][i] >> rgb[2][i];
    }
    dp[0][0] = rgb[0][0]; // 초기 값
    dp[1][0] = rgb[1][0];
    dp[2][0] = rgb[2][0];
    for (int i = 1; i < n;i++){
        dp[0][i] = minum(dp[1][i - 1] + rgb[0][i], dp[2][i - 1] + rgb[0][i]); //0번 색으로 i번 집 색을 칠하는데 드는 최소비용
        dp[1][i] = minum(dp[0][i - 1] + rgb[1][i], dp[2][i - 1] + rgb[1][i]); //1번 색으로
        dp[2][i] = minum(dp[1][i - 1] + rgb[2][i], dp[0][i - 1] + rgb[2][i]); //2번 색으로 
    }
    cout << minum(minum(dp[0][n - 1], dp[1][n - 1]), dp[2][n - 1]);  // 마지막 집에서 3개의 색 중 가장 최소비용인 것 선택
    return 0;
}