[BOJ / C++] RGB 거리 (다이나믹 프로그래밍)

문제링크: https://www.acmicpc.net/problem/1149

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> rgb(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> rgb[i][j];
        }
    }
    
    vector<vector<int>> d(n, vector<int>(3));
    d[0][0] = rgb[0][0];
    d[0][1] = rgb[0][1];
    d[0][2] = rgb[0][2];
    
    for (int i = 1; i < n; i++) {
        d[i][0] = rgb[i][0] + min(d[i-1][1], d[i-1][2]);
        d[i][1] = rgb[i][1] + min(d[i-1][0], d[i-1][2]);
        d[i][2] = rgb[i][2] + min(d[i-1][0], d[i-1][1]);
    }

    cout << min({d[n-1][0], d[n-1][1], d[n-1][2]});
}

 

 

2. 분석

이 문제는 dp 테이블을 잘 잡는 것이 중요하다. dp테이블에서 i번째 rgb를 고정하는 것이 핵심이다. 케이스를 나누려고 생각하면 조건 분기 무한지옥에 빠지게 된다.

 

1. dp 테이블:

d[i][0] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 빨강

d[i][1] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 초록

d[i][2] = i번째 집까지 칠할 때 비용의 최솟값, 단 i번째 집은 파랑  

 

2. 점화식:

d[k][0] = rgb[k][0] + min(d[k-1][1], d[k-1][2])

 

3. 시간복잡도

2차원 배열을 사용하지만 크기가 n*3이므로 이걸 한번만 순회하면서 테이블을 채우므로 O(n)이다. n = 1000 < 10^7 이므로 시간제한 0.5초 이내에 통과 가능하다.