[백준 알고리즘] 1149번 RGB거리

RGB 거리

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

#include<iostream>

using namespace std;

int arr[1001][3];

int dp[1001][3];

int Color(int num, int color)

{

if (num == 1)

{

dp[1][color] = arr[1][color];

return dp[1][color];

}

int a = 0;

int b = 0;

if (color == 0)

{

a = Color(num - 1, 1) + arr[num][0];

b = Color(num - 1, 2) + arr[num][0];

}

if (color == 1)

{

a = Color(num - 1, 0) + arr[num][1];

b = Color(num - 1, 2) + arr[num][1];

}

if (color == 2)

{

a = Color(num - 1, 0) + arr[num][2];

b = Color(num - 1, 1) + arr[num][2];

}

if (a > b)

{

dp[num][color] = b;

}

else {

dp[num][color] = a;

}

return dp[num][color];

}

int main()

{

int num = 0;

cin >> num;

for (int i = 1; i < num+1; i++)

{

cin >> arr[i][0];

cin >> arr[i][1];

cin >> arr[i][2];

}

int min = Color(num, 0);

for (int i = 0; i < 3; i++)

{

if (min > Color(num, i))

{

min = Color(num, i);

}

}

cout << min << endl;

}