[C/C++] 백준 1149번 - RGB거리(DP)

<완전탐색(brute force search) 코드 (시간초과)>

#include<iostream> 
#include<stdio.h>
using namespace std;

int check[1001] = {-1,};
int house[1001][3];
int T, N;
int ans = 1000000000; // 10억

void DP(int x, int sum)
{
	if (x == N + 1)
	{
		if (ans > sum) ans = sum;
		return ;
	}
	for (int i = 0; i < 3; i++)
	{
		if (check[x-1] != i)
		{
			check[x] = i;
			DP(x + 1, sum + house[x][i]);
			check[x] = -1;
		}
	}
}

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		for (int j = 0; j < 3; j++)
			cin >> house[i][j];
	DP(1, 0);
	cout << ans;
	return 0;
}

처음에 문제를 보고 집 개수가 최대 1000개밖에 되지 않으니 모든 경우의 수를 따져보고 가장 작은 값을 출력하면 되겠다고 생각했지만 시간초과였다. 다이나믹 프로그래밍 문제인걸 알고서도 그냥 생각나는대로 코딩하여 실수를 한것같다.

 

 

<DP 코드(정답)>

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

int N;
int DP[1001][3] = { 0, };

int main() 
{
    cin >> N;
    for (int i = 1; i <= N; i++) 
    {
        cin >> DP[i][0] >> DP[i][1] >> DP[i][2];

        DP[i][0] += min(DP[i - 1][1], DP[i - 1][2]); 
        DP[i][1] += min(DP[i - 1][0], DP[i - 1][2]); 
        DP[i][2] += min(DP[i - 1][0], DP[i - 1][1]); 
    }
    
    cout << min(DP[N][0], min(DP[N][1], DP[N][2]) );

    return 0;
}

 

풀이는 각 집의 색칠 비용을 입력 받는 즉시 항상 최소값으로만 값을 저장할 수 있도록 코딩하였고
i=1일때부터 입력값이 아래와 같은 때 차근차근히 코드를 진행해보면 

3
26 40 83
49 60 57
13 89 99

	DP[1][0]	DP[1][1]	DP[1][2]
i = 1	26 + 0	40 + 0	83 + 0

DP[0][0] = DP[0][1] = DP[0][1] = 모두 0 이므로 처음 트라이는 입력받은 값 그래도 저장된다.

 

	DP[2][0]	DP[2][1]	DP[2][2]
i = 2	49 + 40 = 89	60 + 26 = 86	57 + 26 = 83

DP[2][0]의 경우 입력을 49 받고 DP[1]의 요소들 중 DP[1][0]을 제외한 DP[1][1] 과 DP[1][2] 중 작은 값인 40이 더해진다.

DP[2][1]의 경우 입력을 60 받고 DP[1]의 요소들 중 DP[1][1]을 제외한 DP[1][0] 과 DP[1][2] 중 작은 값인 26이 더해진다.

DP[2][2]의 경우 입력을 57 받고 DP[1]의 요소들 중 DP[1][2]을 제외한 DP[1][0] 과 DP[1][1] 중 작은 값인 26이 더해진다.

 

	DP[3][0]	DP[3][1]	DP[3][2]
i = 3	13 + 83 = 96	89 + 83 = 172	99 + 86 = 185

DP[3][0]의 경우 입력을 13 받고 DP[2]의 요소들 중 DP[2][0]을 제외한 DP[2][1] 과 DP[2][2] 중 작은 값인 83이 더해진다.

DP[3][1]의 경우 입력을 89 받고 DP[2]의 요소들 중 DP[2][1]을 제외한 DP[2][0] 과 DP[2][2] 중 작은 값인 83이 더해진다.

DP[3][2]의 경우 입력을 99 받고 DP[2]의 요소들 중 DP[2][2]을 제외한 DP[2][0] 과 DP[2][1] 중 작은 값인 86이 더해진다.

 

따라서 N=3 일때 DP[N][0], DP[N][1], DP[N][2] 값중 가장 작은 값인 96이 정답이 된다. 

 

www.acmicpc.net/problem/1149

1149번: RGB거리