<백준> 1149 RGB 거리 / C++ 풀이

중점:

1. 시간 제한 0.5초

2. 총 합의 최솟값을 구하는 문제

 

풀이:

시간 제한이 0.5초 이며 큰 문제를 작은 부분의 문제로 분할 할 수 있다는 부분에서 DP 알고리즘을 사용해야 겠다고 생각하였다. 여기서 그리디 알고리즘의 사용도 생각해 보았지만 순서의 중복이 안된다는 문제 때문에 최솟값 만을 고르는 것은 전체 정답의 최솟값이 되지 않을 수 있다는 생각을 하게 되었고 DP를 사용하기로 했다. 따라서 R, G, B의 값을 행렬을 통해서 입력받은 후에 각각의 위치에서 최소의 값을 더해가는 반복문을 생각하였다. 위치의 중복이 없고 최솟값을 찾아서 더한 합계의 행렬의 마지막 행에서의 최솟값이 문제가 원하는 정답이다.

 

---

 

정답 코드:

#include <bits/stdc++.h>

using namespace std;

int color[1002][3];
int r[1002], g[1002], b[1002];
int n;

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

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> r[i] >> g[i] >> b[i];
    }

    color[0][0] = r[0];
    color[0][1] = g[0];
    color[0][2] = b[0];

    for (int i = 1; i < n; i++){
        color[i][0] = r[i] + min(color[i - 1][1], color[i - 1][2]);
        color[i][1] = g[i] + min(color[i - 1][0], color[i - 1][2]);
        color[i][2] = b[i] + min(color[i - 1][0], color[i - 1][1]);
    }

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

 

⚙️DP알고리즘 이란?

https://wnehgus101.tistory.com/entry/알고리즘-동적-계획법-DP-Dynamic-Programming

<알고리즘> 동적 계획법 (DP: Dynamic Programming)

 

질문은 댓글로 부탁드립니다. 감사합니다.