[C/C++] 백준 17404: RGB 거리 2

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

17404번: RGB거리 2

17404: RGB 거리 2

 

하나 주의해야 할건 첫번째 칠한 집과 마지막으로 칠한 집의 색깔이 같으면 안되는것이다. 그렇기 때문에 기존의 DP로 문제를 풀게 된다면 이 조건을 만족시키기에 쉽지 않다.

 

 따라서 여기서 생각해야하는건 첫번째로 칠할 집의 색깔을 정하고 나서 for문을 3번 돌며 각각의 경우세어 모든 집을 칠하는 비용의 최솟값을 구해야한다. 즉 dp[0][1]로 시작했을 때는 dp[1][n]과 dp[2][n] 중에 최솟값을 구해야하고 dp[1][1]로 시작했을 때는 dp[0][n]과 dp[2][n]을 dp[2][1]로 시작했을 때는 dp[0][n]과 dp[1][n]을 비교하여서 가장 최소인 값을 출력하면 되는 것이다.

 

 이때 dp[][2]와 dp[][3]을 구하는 것이 문제인데 내가 맨 처음에 생각한 코드는 if문을 이용해 각각의 경우를 적어주었지만 사실은 색칠할 수 없는 집을 굉장히 큰 값을 초기화하고 똑같이 for문을 돌며 min 계산을 넣으면 더 간단하게 풀 수 있다.

 

소스코드!

 

#include<iostream>
#include <algorithm>
#include<queue>
#include<tuple>
#include <string.h>
#include <map>
#include<string>
#include <stack>
#include <limits.h>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int dp[3][1001];
int graph[3][1001];
int road[3][1001];


int main() {  
  ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
    int tmp[3];
    cin>>tmp[0]>>tmp[1]>>tmp[2];
    for(int j=0;j<3;j++)
      graph[j][i]=tmp[j];     
  }
  int result=10000001;
  
  dp[0][1]=graph[0][1];
  dp[1][1]=graph[1][1];
  dp[2][1]=graph[2][1];

  //맨 처음 집이 빨간색일 때
  for(int i=2;i<=n;i++){
    if(i==2){
      dp[1][2]=dp[0][1]+graph[1][2];
      dp[2][2]=dp[0][1]+graph[2][2];
      continue;
    }
    if(i==3){
      dp[0][3]=min(dp[1][2],dp[2][2])+graph[0][3];
      dp[1][3]=dp[2][2]+graph[1][3];
      dp[2][3]=dp[1][2]+graph[2][3];
      continue;
    }
    dp[0][i]=min(dp[1][i-1],dp[2][i-1])+graph[0][i];
    dp[1][i]=min(dp[0][i-1],dp[2][i-1])+graph[1][i];
    dp[2][i]=min(dp[0][i-1],dp[1][i-1])+graph[2][i];    
  }
  int tmp=min(dp[1][n],dp[2][n]);
  result=min(result,tmp);
  


  //맨 처음 집이 초록색일 때
  for(int i=2;i<=n;i++){
    if(i==2){
      dp[0][2]=dp[1][1]+graph[0][2];
      dp[2][2]=dp[1][1]+graph[2][2];
      continue;
    }
    if(i==3){
      dp[0][3]=dp[2][2]+graph[0][3];
      dp[1][3]=min(dp[0][2],dp[2][2])+graph[1][3];
      dp[2][3]=dp[0][2]+graph[2][3];
      continue;
    }
    dp[0][i]=min(dp[1][i-1],dp[2][i-1])+graph[0][i];
    dp[1][i]=min(dp[0][i-1],dp[2][i-1])+graph[1][i];
    dp[2][i]=min(dp[0][i-1],dp[1][i-1])+graph[2][i];    
  }
  tmp=min(dp[0][n],dp[2][n]);
  result=min(result,tmp); 


  //맨 처음 집이 파란색일 때
  for(int i=2;i<=n;i++){
    if(i==2){
      dp[0][2]=dp[2][1]+graph[0][2];
      dp[1][2]=dp[2][1]+graph[1][2];
      continue;
    }
    if(i==3){
      dp[0][3]=dp[1][2]+graph[0][3];
      dp[1][3]=dp[0][2]+graph[1][3];
      dp[2][3]=min(dp[0][2],dp[1][2])+graph[2][3];
      continue;
    }
    dp[0][i]=min(dp[1][i-1],dp[2][i-1])+graph[0][i];
    dp[1][i]=min(dp[0][i-1],dp[2][i-1])+graph[1][i];
    dp[2][i]=min(dp[0][i-1],dp[1][i-1])+graph[2][i];    
  }
  tmp=min(dp[0][n],dp[1][n]);
  result=min(result,tmp);
  
  cout<<result;  
  
}