[c++] 백준 1149 RGB거리

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

1149번: RGB거리

dp로 풀 수 있는 문제이다.

문제의 난이도 표기가 다른 문제들에 비해 높은 편이지만

dp 테이블의 정의를 정확히 정의해 준다면

이 문제는 굉장히 쉬워진다.

 

문제에서 요구하는 사항을 보자.

 

1. 이웃하는 집은 색이 같지 않아야 한다.
2. 집을 칠하는 최소 비용을 구하자.

그럼 이 조건들을 보며 dp 테이블을 어떻게 정의할지 생각해 보자.

i번째 집을 선택해야 하는 단계라고 가정하자.

 

우리는 이 집을 R, G, B 세 가지의 색으로 칠할 수 있다.

i번째 집을 R로 칠할 때에는 i-1번째 집을 G, B로 칠했어야 한다.

i번째 집을 G로 칠할 때에는 i-1번째 집을 R, B로 칠했어야 한다.

i번째 집을 B로 칠할 때에는 i-1번째 집을 R, G로 칠했어야 한다.

 

이런 상태를 모두 정의할 수 있는 dp 테이블은 2차원 dp 테이블 이어야 한다.

따라서 다음과 같이 dp 테이블을 정의한다.

dp[i][j] : i번째 집을 j색으로 칠할 때 최소 비용

 

위에서 언급한 i번째 집을 칠하는 방법을 점화식으로 구현해 주면 다음과 같다.

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2]

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,dp[1010][3],a[1010][3];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i][0]>>a[i][1]>>a[i][2];
    for(int i=0; i<3; i++)
        dp[1][i] = a[1][i];
    for(int i=2; i<=n; i++){
        dp[i][0] = min(dp[i-1][1],dp[i-1][2])+a[i][0];
        dp[i][1] = min(dp[i-1][0],dp[i-1][2])+a[i][1];
        dp[i][2] = min(dp[i-1][0],dp[i-1][1])+a[i][2];
    }
    cout << min({dp[n][0],dp[n][1],dp[n][2]});
    return 0;
}