[C언어] 백준알고리즘 1149 RGB거리 문제

문제

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

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

입력

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

출력

첫째 줄에 모든 집을 칠할 때 드는 비용의 최솟값을 출력한다.

int arr[3];
int dp[3];
int dp2[3];
int Min(int a, int b)
{
    return a < b ? a : b;
}
void distance_RGB(int N)
{
    int i;
    dp[0] = dp[1] = dp[2] = 0;
    for (i = 1; i <= N; i++)
    {
        scanf("%d %d %d", &arr[0], &arr[1], &arr[2]);
        //임시저장 변수
            dp2[0] = dp[0];
            dp2[1] = dp[1];
            dp2[2] = dp[2];
        //DP 계산
            dp[0] = Min(dp2[1], dp2[2]) + arr[0];
            dp[1] = Min(dp2[0], dp2[2]) + arr[1];
            dp[2] = Min(dp2[0], dp2[1]) + arr[2];
    }
    int min = Min(Min(dp[0], dp[1]), dp[2]);
    printf("%d", min);
}
int main()
{
    int i;
    int N;
    scanf("%d", &N);
    distance_RGB(N);
}

일단 나는 배열3개를 사용하였다.

입력받는배열 3개와 dp를 계산할 배열 1,2 이다.

일단 기본적인 문제푸는방법은

3
26 40 83
49 60 57
13 89 99

입력이라면 

일단

처음엔 

26 40 83 을 받는다 그이후

같은 색은 못칠하므로 그다음 번째에서 0번째(R)는 1,2 번째(G,B) 배열중 작은값과 이전에 계산된 dp값에 더하면된다.

1번째는 0,2 번째와 2번째는 0,1번째와 비교하여 그전의 dp값과 계속 비교하면서 구하면된다.

처음엔 dp에 26 40 83 이 저장될것이다 그전의 계산된 값이 없으므로

그다음엔 dp[0] 에는 dp[1],dp[2] 값중 더 작은값과 R값을 더한다.

나머지도 그런식으로 계산하여 dp[0~~3] 값중 최소값을 출력하면 된다.