1149>RGB 거리

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

동적계획법

문제 RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.

code>>

#include<stdio.h>

#include<algorithm>

#include<string.h>

using namespace std;

int dp[1001][3];

int house[1000][3] = { { 26, 40, 83 },{ 49,60,57 },{ 13,89,99 } };

int GetSolve(int idx, int color, int size)

{

if (idx >= size)return dp[idx][color] = house[idx-1][color];

if (dp[idx][color] != -1) return dp[idx][color];

int value = 987654321;

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

{

if (color == i) continue;

value = std::min(GetSolve(idx + 1, i, size), value);

}

return dp[idx][color] = value + house[idx -1][color];

}

int main()

{

int size = 3;

scanf("%d", &size);

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

{

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

{

scanf("%d", &house[i][ii]);

}

}

memset(dp, -1, sizeof(dp));

int min = 987654321;

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

{

min = std::min(GetSolve(1, i, size), min);

}

printf("%d\n", min);

    return 0;

}