[C++] BOJ_1149 RGB 거리

문제: 백준 1149 (c++)

풀이과정

---

처음 조건만 잘 본다면 생각보다 쉽게 점화식을 찾아낼 수 있다.

집에 색을 칠하는 조건이 총 세 가지가 나와 있는데 결국 각 집이 앞뒤 색상이 달라야 한다는 말이다.

그렇기에 처음 시작을 세 가지 경우로 나누는 것으로 접근하면 된다.

---

0, 1, 2가 빨강, 초록, 파랑이기에 min 함수를 이용하여

배열이 dp[i][0]일 경우는 1 또는 2를

배열이 dp[i][1]일 경우는 0 또는 2를

배열이 dp[i][2]일 경우는 0 또는 1을 선택하는 경우를 나누어 생각하면 된다.

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

int main(){
    
    int n ;
    cin >> n ;

    int dp[1001][3] ;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < 3; j++){
            cin >> dp[i][j] ;
        }
    }

    for(int i = 0; i < n; i++){
        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]) ;
    }

    int res = min(dp[n-1][0], min(dp[n-1][1], dp[n-1][2])) ;

    cout << res ;
}