[백준 1149번] RGB거리 (C++)

https://www.acmicpc.net/problem/1149

1149번: RGB거리

가장 최소 비용을 구해야 하므로, 최소~ 하면 그리디나 그래프 탐색이 떠오르지만 앞의 두 알고리즘으로 코드를 짜는게 불가능하다.(가능할 수도 있겠지만 너무 산으로 간다는 뜻)

흔히 DP라고 불리는 다이나믹 프로그래밍이라고 불리는 알고리즘을 사용해야하는 문제로 DP는 그리디나, 수학문제 처럼 정해진 알고리즘을 사용하면 딱 풀리는 알고리즘이 아니라 생각이 필요한 알고리즘이다.

 

DP문제를 풀려면 흔히 점화식를 작성하라고 하는데, 점화식은 고등학교 과정에서 수열파트에서 접해보았을 것이다.

수열의 앞, 뒤 또는 두칸 앞 등 앞이나 뒤의 숫자에 의해서 현재 구하고자 하는 숫자를 표현한 식을 점화식이라고 했다.

DP도 마찬가지로 DP배열 앞의 원소 또는 뒤의 원소에 의해서 현재 원소에 어떤것이 들어갈지 정한다.

 

거기에 브루트포스가 합쳐졌다고 생각하면 된다. 

발생할 수 있는 모든 경우의 수를 다 탐색하여 최적의 경우를 DP배열에 넣는 것이다. 하지만 말했다시피 DP배열의 앞 또는 뒤 원소에 의해서 원소가 정해지다 보니 규칙만 안다면(점화식만 구해졌다면) 기본적인 연산으로 원소를 구할 수 있어서 모든 경우의 수를 다 탐색해도 순수한 Bruteforce보다 오래걸리지 않는다. 

시간을 줄이는 대신 DP배열을 생성했기 때문에 메모리가 더 많이든다.

 

한마디로 메모리를 늘려서 연산을 빠르게 한다. 라고 생각하면 된다.

 

코드는 다음과 같다.

빨간색을 선택했을때, 초록색을 선택했을때, 파란색을 선택했을때 각각 결과가 어떻게 나오는지를 모두 탐색하고 그중에서 가장 작은 경우를 출력한다.

이번 문제 같은 경우는 예제의 for문이 3번밖에 안돌기 때문에 손으로 직접 한번 써보는 것도 이해하는데 도움이 된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main(void){
  ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
  int n, color;
  cin >> n;
  vector<vector <int>> house(n,vector<int>(3));
  vector<vector <int>> dp(n,vector<int>(3));
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 3; j++){
      cin >> house[i][j];
    }
  }
  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++){
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house[i][0];
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house[i][1];
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house[i][2];
  }
  cout << *min_element(dp[n-1].begin(), dp[n-1].end());
}