[백준 1149] RGB거리

문제

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

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

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

입력

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

출력

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

예제 입력

3
26 40 83
49 60 57
13 89 99

예제 출력

96

사실 알고리즘적 요소보다 문제 이해가 어려웠다.

문제 이해만 빠르고 확실하게 한다면 어려움없이 풀 수 있는 문제다.

만약 빨간집으로 시작했다면 2번째 집은 초록 or 파랑 이여만 한다.

즉 dp[0][1] (빨간색으로 칠했을때) = min(dp[1][i-1], dp[2][i-1])(전 집에서 초록색을 칠했을떄의 최소비용과 파란색으로 칠했을 떄의 최소비용 중 최소값) + r_cost (현재 i를 빨간색으로 칠했을때의 비용)

dp[1][1] (초록색으로 칠했을때) = min(dp[0][i-1], dp[1][i-1])(전 집에서 빨간색을 칠했을떄의 최소비용과 파란색으로 칠했을 떄의 최소비용 중 최소값) + g_cost (현재 i를 초록색으로 칠했을때의 비용)

dp[2][1] (파란색으로 칠했을때) = min(dp[0][i-1], dp[1][i-1])(전 집에서 빨간색을 칠했을떄의 최소비용과 초록색으로 칠했을 떄의 최소비용 중 최소값) + b_cost (현재 i를 파란색으로 칠했을때의 비용)

와 같은 식으로 진행되는 것을 알 수 있다.

이와 같은 식으로 모든 비용을 구한 이후 최소값을 출력해주는 알고리즘이다.

소스

// //  main.cpp //  DP // //  Created by seungwoo on 2018. 3. 29.. //  Copyright © 2018년 seungwoo. All rights reserved. // #include <iostream> #include <algorithm> using namespace std; int main(int argc, const char * argv[]) {     int house;     int result;     int cost[3][1001]={0};     cin>>house;     for(int i=1; i<=house; i++){         int r_cost, g_cost, b_cost;         cin>>r_cost>>g_cost>>b_cost;         cost[0][i] = min(cost[1][i-1] , cost[2][i-1]) + r_cost;         cost[1][i] = min(cost[0][i-1] , cost[2][i-1]) + g_cost;         cost[2][i] = min(cost[0][i-1] , cost[1][i-1]) + b_cost;     }     result = min(cost[0][house], min(cost[1][house],cost[2][house]));     cout<<result;     return 0; }