(1149) RGB거리

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

단계별로 풀어보기

21단계(동적 계획법 1) 6번째

 

 

 

dp[k][0], dp[k][1], dp[k][2]를 k번째 집까지 칠했으며 k번째 집을 각각 빨강, 초록, 파랑으로 칠했을 때의 최소 비용이라고 하자.

k=1일 때 각각의 dp값은 첫 번째 집을 칠하는 비용과 같다.

k>1일 때 dp[k][0]을 생각하면 k번째 집을 빨강으로 칠하려면 k-1번째 집은 빨강으로 칠했으면 안 되고 초록이나 파랑으로 칠해야 한다. 따라서 dp[k][0]은 k번째 집을 빨강으로 칠하는 비용에 dp[k-1][1]과 dp[k-1][2] 중 작은 값을 더한 값이다.

dp[k][1]과 dp[k][2]도 같은 방식으로 생각할 수 있으며, 마지막까지 계산한 뒤 dp[n][0], dp[n][1], dp[n][2] 중 작은 값이 정답이다.

 

 

 

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector v(n+1, vector<int> (3)), dp= v;
  
  for(int i=1;i<=n;i++){
    for(int j=0;j<3;j++){
      cin >> v[i][j];
    }
  }
  
  dp[1][0]= v[1][0];  dp[1][1]= v[1][1];  dp[1][2]= v[1][2];
  
  for(int i=2;i<=n;i++){
    dp[i][0]= v[i][0] + min(dp[i-1][1], dp[i-1][2]);
    dp[i][1]= v[i][1] + min(dp[i-1][0], dp[i-1][2]);
    dp[i][2]= v[i][2] + min(dp[i-1][0], dp[i-1][1]);
  }
  
  cout << min(min(dp[n][0], dp[n][1]), dp[n][2]);
  
  return 0;
}

 

 

 

사실 dp를 풀 때 모든 값이 필요한 것은 아니다. 이 문제의 점화식을 보면 알겠지만 k에서 dp값을 구할 때 필요한 것은 k-1일 때 dp값이지 그 이전 값들은 필요없기 때문이다. 따라서 굳이 n*3개의 값을 저장하는 dp배열을 만들 필요 없이, 이전 dp값만 저장하는 3개의 변수만 있어도 충분하다.

어려운 DP문제의 경우 공간 복잡도도 최적화해야 하는 경우가 있는데, 그럴 때 필요한 테크닉이다.

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

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, r, g, b;
  
  cin >> n >> r >> g >> b;
  
  for(int i=1;i<n;i++){
    int x, y, z;
    
    cin >> x >> y >> z;
    
    x+= min(g, b);  y+= min(r, b);  z+= min(r, g);
    r= x;  g= y;  b= z;
  }
  
  cout << min(min(r, g), b);
  
  return 0;
}