[BOJ]1146_RGB거리

1146번 RGB거리

RGB거리

📍 시간 초과 난 풀이

재귀함수로 구현하여 시간 복잡도는 O(2^N)이다.
예를 들어 N = 1000인 경우 계산이 불가능한 수준이다.

#include <iostream>
#include <vector>

#define MAX 1001

using namespace std;

int Nminimum=987654321;
int house[MAX][3];
void bfs(int now, int level , int total,string s){

  if(level == N ){
 // cout<<now<<","<<level<<","<<total<<","<<s<<endl;
    minimum = min(minimum,total);
    return;
  }
  
  if(s[now-1] == '0' ){
    bfs(now+1,level+1,total+house[now+1][1],s+"1");
    bfs(now+1,level+1,total+house[now+1][2],s+"2");
  }else if(s[now-1] == '1'){
    bfs(now+1,level+1,total+house[now+1][0],s+"0");
    bfs(now+1,level+1,total+house[now+1][2],s+"2");
  }else if(s[now-1] == '2'){
    bfs(now+1,level+1,total+house[now+1][0],s+'0');
    bfs(now+1,level+1,total+house[now+1][1],s+'1');
  }
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> N;
    for(int i = 1 ; i <= N ; i++ ){
      cin >> house[i][0] >>house[i][1] >>house[i][2] ;
    }
    
    bfs(1,1,house[1][0],"0");
    bfs(1,1,house[1][1],"1");
    bfs(1,1,house[1][2],"2");
    
    cout<<minimum;
    return 0;  
}

따라서 동적프로그래밍으로 해결해야한다.

✨ 정상 풀이

빨강, 파랑, 초록 세 가지 색깔중 연속한 두 집의 색은 같지 않아야한다.
빨강을 골랐을 때는 초록과 파랑 중 가중치가 낮은 것을 골라 두 가중치의 합을 더해서 넣어준다. 파랑 또는 초록을 골랐을 경우에도 마찬가지로 나머지 두 색에 대해서 비교하여 가중치가 낮은 색과 수를 합해 더한 값을 넣어준다.
이를 i가 N이 될 때까지 반복하여 반복문 탈출 후에는 마지막 배열들 중에서 가장 낮은 값이 정답이다.

#include <iostream>
#include <vector>

#define MAX 1001

using namespace std;

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