[DP]백준1149번 RGB거리

백준1149 RGB거리

아직 DP가 익숙하지 않아 많이 헷갈렸다.

다만 DP 문제를 풀 때, 한 가지 잘 생각해야 하는 점은

DP는 어떤 하나의 케이스를 고르는 것이 아니라, 모든 케이스를 저장하며 가는 것이다.”

이 문제의 경우는, 각 집 별로 세 가지의 경우가 있다.

집을 빨간색, 초록색, 파란색으로 칠하는 경우이다.

따라서 각 집 별로 모든 경우의 수를 계산하면서 가면 된다.

이 때, 헷갈리는 조건은

• i(2 ≤ i ≤ N-1) 번 집의 색은 i-1번, i+1 번 집의 색과 같지 않아야 한다.

는 것이었는데, i-1과 i+1의 색이 달라야 한다는 말은 없다.

따라서 우리는 dp의 점화식을 구성할 때 당장 직전에 고른 것만 피해가면 되는 것이다.

dp 배열 : 집을 각 색깔 별로 칠하는데 드는 비용

초기값:

첫 번째 집의 정답 배열[빨강] = 첫 번째 집을 칠하는 비용[빨강]

첫 번째 집의 정답 배열[초록] = 첫 번째 집을 칠하는 비용[초록]

첫 번째 집의 정답 배열[파랑] = 첫 번째 집을 칠하는 비용[파랑]

점화식

//현재 보고 있는 집 i

i 번째 집을 빨간색으로 칠하는데 드는 총 비용 : 
	min(i-1번째 집을 초록색으로 칠하는 경우, i-1번째 집을 파란색으로 칠하는 경우) +
	i 번째 집을 빨간색으로 칠하는데 드는 비용

i 번째 집을 초록색으로 칠하는데 드는 총 비용 : 
	min(i-1번째 집을 빨간색으로 칠하는 경우, i-1번째 집을 파란색으로 칠하는 경우) +
	i 번째 집을 초록색으로 칠하는데 드는 비용

i 번째 집을 파란색으로 칠하는데 드는 총 비용 : 
	min(i-1번째 집을 빨간색으로 칠하는 경우, i-1번째 집을 초록색으로 칠하는 경우) +
	i 번째 집을 파란색으로 칠하는데 드는 비용

모든 집을 칠한 다음에는 마지막 집의 dp 배열에서 최솟값을 출력한다.

마지막 집의 dp 배열 :
[0] : 마지막 집을 빨간색으로 칠하는데 드는 총 비용
[1] : 마지막 집을 초록색으로 칠하는데 드는 총 비용
[2] : 마지막 집을 파랑색으로 칠하는데 드는 총 비용

cout << min(dp[마지막][0], dp[마지막][1], dp[마지막][2]);

#include <iostream>
#include <algorithm>
using namespace std;

int houses[1005][3];
int answer[1005][3];
int tmp[2];
int main(){
    int N;
    cin >> N;
    
    for(int i=1;i<=N;i++){
        for(int j=0;j<3;j++){
            cin >> houses[i][j];
        }
    }
    answer[1][0] = houses[1][0];
    answer[1][1] = houses[1][1];
    answer[1][2] = houses[1][2];
    
    for(int i=2;i<=N;i++){
        answer[i][0] = min(answer[i-1][1] , answer[i-1][2]) + houses[i][0];
        answer[i][1] = min(answer[i-1][0] , answer[i-1][2]) + houses[i][1];
        answer[i][2] = min(answer[i-1][0] , answer[i-1][1]) + houses[i][2];
    }
    
    cout << min({answer[N][0], answer[N][1] , answer[N][2]});
    
    
    
}