백준 1149 - RGB거리

문제 설명

 

=> DP문제입니다. 

=> 오랜만에 푸는 문제인지라 이해하는데 오래 걸렸습니다. 

 

=> 빨간색을 칠하기 위해서는 이전에 초록색 혹은 파란색이 칠해져 있어야 합니다. 

=>이 경우, 둘 중에 최소값을 골라 해당하는 집에 빨간색을 칠하는 금액에 더해주어야 합니다. 

 

 

 

파랑 or 초록 (1번째 집)

빨강 (2번째집)

=> 위의 방식처럼 이루어져야 합니다. 

=>2번째 집에 빨강을 칠하고 싶을 경우, 이전의 집의 색이 파랑 혹은 초록이어야 합니다. 

 

 

 

**주의할 점 : row가 0인 지점부터 값을 넣어줄 경우 (0-1) 지점을 참조할 수 있으니 실수하지 않도록 합니다. 

 

 

 

점화식은 아래와 같습니다. 

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

 

 

 

<code>

#include <iostream>
#include <algorithm>


using namespace std;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int dp[1001][3] ={0}; //이전값을 더해주는 경우를 위해 초기화를 0으로 해준다.
    
    int N;
    cin >> N;
    
    //dp [i][0] : R ,dp [i][1] : G, dp [i][2] : B
    
    for(int i=1; i<=N; i++)
    {
        cin >> dp[i][0] >>dp[i][1] >> dp[i][2];
        
        dp[i][0] += min(dp[i-1][1] , dp[i-1][2]);
        dp[i][1] += min(dp[i-1][0] , dp[i-1][2]);
        dp[i][2] += min(dp[i-1][0] , dp[i-1][1]);
        
    }
    
    cout << min(dp[N][0], min(dp[N][1], dp[N][2]))<<'\n';
    
    
    return 0;
}

 

 

실행 화면 1

 

실행 화면 2