12주차(동적계획) - [C++]백준1149 RGB거리

27 Nov 2022 in Study on Algorithm

백준1149 RGB거리 링크

문제

예제 입력

---

코드

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

int rgb[1001][3];
int dp[1001][3];
int n;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    for (int i = 1; i <= n; i++) {
        dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + rgb[i][0];
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + rgb[i][1];
        dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + rgb[i][2];
    }
    cout << min({ dp[n][0], dp[n][1], dp[n][2]});
}

설명

이 문제는 다이나믹 프로그래밍, 동적계획(dp) 알고르즘은 워낙 어려운 알고리즘이고 중요한 알고리즘이여서 많은 시간을 투자해야 되는 알고리즘입니다. 그리디 알고리즘과 비슷하게 여러개의 작은 하위 문제로 나누어 푼 다음 결합하여 최종적인 목적에 도달하는 것이고 차이점은 greedy는 근사해를 구해주는 반면에 dp는 최적해를 구해줍니다. 문제를 풀때 팁은 아래와 같습니다.

 1. 점화식 찾기
 2. top-down(memoization) 
 3. bottom-up

memoization 방식으로 문제를 생각하여 앞으로 남은 선택들에 해당하는 비용만을 반환하도록 부분 문제 정의를 변경합니다. 최적해를 구하기 위해선 모든 답을 만들어보고 그 중 최적해를 반환하는 완전 탐색으로 설계합니다. 재귀 호출의 입력 이전의 선택에 관련된 정보가 있다면 필요한 것만 남기고 줄입니다.

---

예시

피보나치 수열
0-1 배낭 문제
배낭 짐싸기 문제
최장증가수열(LIS)
외판원 순회 문제(TSP)

---

결과