1) 문제 분석
DP 문제라는걸 몰랐으면 풀지 못했을 것 같은 문제. 두 번째 집부터 차례로 해당 집을 빨간색, 초록색, 파란색으로 칠했을 때의 각각의 경우의 최솟값을
계속 구해주면 된다. 예를 들어, i번째 집에서 우선 빨간색을 칠한다고 가정하면, i-1번째 집은 파란색, 초록색만 칠할 수 있으며 i-1번째 집을 파란색으로 칠한 경우의
최솟값과 초록색으로 칠한 경우의 최솟값 중 더 작은 값에 i번째 집을 빨간색으로 칠하는 값을 더한 값이 i번째 집을 빨간색으로 칠하는 경우의 최솟값이 된다.
식으로 나타내면 다음과 같다
red_min[i] = min(green_min[i-1],blue_min[i-1])+red[i];
green_min[i] = min(red_min[i-1],blue_min[i-1])+green[i];
blue_min[i] = min(red_min[i-1],green_min[i-1])+blue[i];
실제 코드에서는 모든 i번째 집에서의 각 색의 최솟값들을 배열로 저장해줄 필요는 없다.
이렇게 값을 다 구하면, 각 색의 최솟값들 중 가장 작은 값이 답이 된다.
2) 코드
#include <iostream>
using namespace std;
int N; //집의 수
int house[1000][3]; //각 집의 칠하는 가격
int cost; //최소 가격
int rgb[3]; //마지막 집을 빨강, 초록, 파란색으로 칠했을 때의 최소 가격
int main(){
int red, green, blue;
cin >> N;
for(int i=0; i<N; i++){
for(int j=0; j<3; j++)
cin >> house[i][j];
}
//첫 집의 각 색으로 칠하는 가격
rgb[0]=house[0][0];
rgb[1]=house[0][1];
rgb[2]=house[0][2];
//두 번째 집 부터 rgb 각 색으로 마지막 집을 칠했을 때의 최소 가격을 rgb 배열에 저장한다
for(int i=1; i<N; i++){
red = rgb[1]<rgb[2]?rgb[1]:rgb[2]; red+=house[i][0]; //i번째 집을 빨간색으로 칠한 경우
green = rgb[0]<rgb[2]?rgb[0]:rgb[2]; green+=house[i][1]; //i번째 집을 초록색으로 칠한 경우
blue = rgb[0]<rgb[1]?rgb[0]:rgb[1]; blue+=house[i][2]; //i번째 집을 파란색으로 칠한 경우
rgb[0]=red; rgb[1]=green; rgb[2]=blue;
}
//최솟값을 구한다
cost = rgb[0]<rgb[1]?rgb[0]:rgb[1];
cost = cost<rgb[2]?cost:rgb[2];
cout<<cost;
}