1149 RGB거리 - C++

[pykido]

풀이과정

• 문제 해결의 흐름

1. 우선, 문제 설명을 읽고 나서 DP 문제일 거 같다는 느낌이 강하게 들었습니다.
   • 동적계획법, DP(Dynamic Programming)이란?
     • 중복되는 계산 결과를 저장하여 복잡한 문제를 더 작은 하위 문제들로 나누어 해결하는 기법입니다.
     • 이 기법은 다음 2가지 특징을 가진 문제에서 주로 사용됩니다!
       • 최적 부분 구조 : 문제를 작은 부분 문제들로 나누어 부분 문제들의 최적해를 구하여 최종적으로 전체 문제의 최적해를 구할 수 있는 구조
       • 중복 부분 문제 : 동일한 부분 문제가 여러 번 반복되어 나타나는 구조
2. 이 문제를 DP로 접근해야하는 이유는 이웃한 집의 색깔은 서로 달라야하는 조건 하에 모든 집을 칠할 최적의 비용을 구해야하기 때문입니다.
3. 점화식은 다음과 같습니다.

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

문제 풀이 코드 및 후기

오랜만에 푸는 DP문제인데, 점화식을 생각보다 쉽게 구할 수 있어서 금방 풀었던 거 같습니다!

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    // 0. 입력 받기
    int N;
    cin >> N; // 집의 수, 2 <= N <= 1000
    int house[1001][3] = {0,};
    for (int i = 0; i < N; ++i) {
        int r,g,b;
        cin >> r >> g >> b;
        house[i][0] = r;
        house[i][1] = g;
        house[i][2] = b;
    }

    // 1. 점화식 이용해서 풀기
    int dp[1001][3] = {0}; // DP 배열 초기화
    dp[0][0] = house[0][0];
    dp[0][1] = house[0][1];
    dp[0][2] = house[0][2];
    for (int i = 1; i < N; ++i) { // O(N)
        dp[i][0] = house[i][0] + min(dp[i-1][1] , dp[i-1][2]);
        dp[i][1] = house[i][1] + min(dp[i-1][0] , dp[i-1][2]);
        dp[i][2] = house[i][2] + min(dp[i-1][0] , dp[i-1][1]);
    }

    // 2. 출력하기
    cout << min(min(dp[N-1][0] , dp[N-1][1]) , dp[N-1][2]);

    return 0;
}

[stopmin]

DP의 신 김태윤이 돌아왔다..!!

[amm0124]

잘봤습니다!!