[백준] No.1149 - RGB거리 (C++)

문제

www.acmicpc.net/problem/1149

1149번: RGB거리

 

풀이

 

전형적인 다이나믹 프로그래밍 문제이다. 이런 문제의 특징인 부르트 포스로 모두 계산하기에는 경우의 수가 너무 많다. 이러한 경우의 수들 중 중복계산을 수도 없이 호출하기 때문에 우리는 계산된 값들을 저장하여 최적화를 할 수 있다.

 

해당 문제에서 모든 집들을 단순히 3가지 색으로 칠하는 경우의 수는 3^1000 이므로 시간 초과가 발생한다.

하지만 메모이제이션으로, 해당 순서의 집이 특정 색으로 칠해진 경우의 최솟값을 저장하면 3(3가지 색) * N(집의 개수)인 경우의 수만 계산하면 된다. 

 

특히 이를 구현하기 위해서 우리는 부분 문제를 top_down(탑 다운)방식으로 해결하였다.

 

*top_down(탑 다운)에 대해서 모르겠다면 라이님의 블로그를 참조하자.*

다이나믹 프로그래밍의 top_down과 bottom-up에 관하여

 

즉, 가장 큰 문제인 첫 번째 집을 어떤 색으로 칠할지부터 시작하여 재귀 호출로 차례로 내려간다.

 

기저 조건: 마지막 집인 house_num -1에 도달한다면 paint_costs[house_idx][color_num]를 바로 반환

 

 해당 집이 color_num로 색칠한 값이 이미 존재한다면 min_cost[house_idx][color_num] (이후 ret)는 -1이 아니기 때문에 그 값을 바로 반환하여 중복계산을 방지한다.

 

 만약 ret가 -1이라면 아직 계산하지 못한 값이기 때문에 지금 집이 칠해진 색(color_num)을 제외하고 다음 집을 칠해본다. 이 값들에 지금 집(house_idx)을 해당 색(color_num)으로 칠한 값(paint_costs[house_idx][color_num])과 더하여 다음 집을 어떤 색으로 칠할 경우 최소 비용이 구해지는 계산 한다. 

 

계산 결과를 ret에 저장한 후 이를 반환하면 메모이제이션의 구현이 가능해진다.

 

 

코드

추가적으로 for문으로만 이루어진 bottom-up 방식으로 구현하면 아래와 같다.

bottom-up 방식은 재귀함수를 호출하지 않기때문에 실행속도가 빠르지만 재귀함수처럼 직관적이지 않아 코드를 작성하기 힘든 편이다.

 

#include <iostream>
#include<string.h>
using namespace std;
 
int house_num;
int paint_costs[1000][3];
int min_cost[1000][3];
 
int main() { 
  cin>>house_num;
 
  for(int i=0; i<house_num ; ++i)
    for(int j=0; j<3 ; ++j)
      cin>>paint_costs[i][j];
 
  min_cost[house_num -1][0] =paint_costs[house_num -1][0];
  min_cost[house_num -1][1] =paint_costs[house_num -1][1];
  min_cost[house_num -1][2] =paint_costs[house_num -1][2];
 
  int min;  
  for(int idx = house_num -2; idx>=0 ; --idx){
    for(int color_num=0; color_num<3 ; ++color_num){
      min = 10000000;
      for(int pre_color=0; pre_color<3 ; ++pre_color){
        if(pre_color == color_num)
          continue;
        min = min < min_cost[idx+1][pre_color] ? min:min_cost[idx+1][pre_color];
      }
      min_cost[idx][color_num] = min + paint_costs[idx][color_num];
    }
  }
 
  min=10000000;
  for(int i=0; i<3 ; ++i){
    
    min = min< min_cost[0][i] ? min : min_cost[0][i];
  }
  cout<<min<<'\n';
 
  return 0;
}