(17404) RGB거리 2

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

단계별로 풀어보기

40단계(동적 계획법 3) 5번째

 

 

 

예전에 풀었던 RGB거리 문제인데 집이 원형이라 1번 집과 N번 집의 색깔도 달라야 하는 문제.

원형 DP문제는 처음과 마지막의 관계에 따라 경우를 나눈 뒤 선형으로 풀면 된다.

이 문제에서 예를 들면 처음 집을 특정 색으로 칠한 뒤 마지막 DP값 중 처음 집과 같은 색으로 칠한 경우를 제외하고 나머지 경우에서만 답을 비교하면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1000001

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, ans= INF;
  
  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]= INF;  dp[1][2]= INF;
  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]);
  }
  ans= min({ans, dp[n][1], dp[n][2]});
  
  dp[1][0]= INF;  dp[1][1]= v[1][1];  dp[1][2]= INF;
  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]);
  }
  ans= min({ans, dp[n][0], dp[n][2]});
  
  dp[1][0]= INF;  dp[1][1]= INF;  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]);
  }
  ans= min({ans, dp[n][0], dp[n][1]});
  
  cout << ans;
  
  return 0;
}