[백준 c++] 1149 RGB거리 (실1)

📌 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

처음에 이 문제를 DFS로 풀었다. 풀린다... 하지만 시간초과... 왜일까 고민해봤다

#include <iostream>

using namespace std;

int MIN = 999000;
int N;
int Red[1001];
int Green[1001];
int Blue[1001];

//DP로 이전 값 저장
int total[1001][3];

//DFS search
void Search(int Before, int idx){
    
    //끝일 경우
    if(idx == N){
        if(MIN > total[idx -1][Before]) MIN = total[idx -1][Before];
        return;
    }
    
    //앞이 Red일 경우
    if(Before == 0){
        
        //Green 색칠
        total[idx][1] = total[idx-1][Before] + Green[idx];
        Search(1, idx + 1);
        
        //Blue 색칠
        total[idx][2] = total[idx-1][Before] + Blue[idx];
        Search(2, idx + 1);

    }
    //앞이 Green일 경우
    else if(Before == 1){
        
        //Red 색칠
        total[idx][0] = total[idx-1][Before] + Red[idx];
        Search(0, idx + 1);
                
        //Blue 색칠
        total[idx][2] = total[idx-1][Before] + Blue[idx];
        Search(2, idx + 1);
    }
    //앞이 Blue일 경우
    else if(Before == 2){
        
        //Red 색칠
        total[idx][0] = total[idx-1][Before] + Red[idx];
        Search(0, idx + 1);
        
        //Green 색칠
        total[idx][1] = total[idx-1][Before] + Green[idx];
        Search(1, idx + 1);
        
    }
}

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++) cin >> Red[i] >> Green[i] >> Blue[i];
    
    total[0][0] = Red[0];
    total[0][1] = Green[0];
    total[0][2] = Blue[0];
    //search 
    Search(0,1);
    Search(1,1);
    Search(2,1);
    
    //output
    cout << MIN << endl;

    return 0;
}

문제의 코드인데 DFS 코드가 최적화가 안 되어 있는가? 계속 수정해봤지만 아무리 생각해도 알 수 없다 으악!

 

But, 시간복잡도를 생각해보자.

첫번째 집은 선택할 수 있는 집은 3개고 그 이후 2~N까지의 집은 총 2개의 선택지가 있으므로,

시간복잡도는 3 X 2^(N-1) => O(2^N)...

비효율적인 방법임을 깨달았다... 이런ㅠ

 

이 문제는 DP로 풀 수 있다.. DP로 이전의 최소값을 배열에 저장하고 이를 계속 저장해나가는 작업을 반복하면

N바퀴만 탐색을 하면되기 때문에 시간복잡도는 O(N)이다.. 이럴수가...

이래서 시간복잡도를 미리 생각해보고 문제를 푸는 것이 중요하다

 

💻 정답 코드

#include <iostream>
using namespace std;

int MIN;
int N;
int Red[1001];
int Green[1001];
int Blue[1001];

//DP로 이전 값 저장
int total[1001][3];

int main()
{
    cin >> N;
    for(int i = 0; i < N; i++) cin >> Red[i] >> Green[i] >> Blue[i];
    
    total[0][0] = Red[0];
    total[0][1] = Green[0];
    total[0][2] = Blue[0];
    //search 
    
    
    for(int i = 1; i < N; i++){
        
        total[i][0] = total[i-1][1] < total[i-1][2] ? total[i-1][1] : total[i-1][2];
        total[i][0] += Red[i];
        
        total[i][1] = total[i-1][0] < total[i-1][2] ? total[i-1][0] : total[i-1][2];
        total[i][1] += Green[i];
        
        total[i][2] = total[i-1][0] < total[i-1][1] ? total[i-1][0] : total[i-1][1];
        total[i][2] += Blue[i];
    }

    MIN = total[N-1][0] < total[N-1][1] ? total[N-1][0] : total[N-1][1];
    MIN = total[N-1][2] < MIN ? total[N-1][2] : MIN;
    
    //output
    cout << MIN << endl;

    return 0;
}