[BOJ] 1149번 RGB거리 (C++)

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

1149번: RGB거리

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int house[1001][3];
 
int main() {
	int n;
	cin >> n;
 
	int r, g, b;
	for(int i = 1; i <= n; i++){
		cin >> r >> g >> b;
		house[i][0] = min(house[i - 1][1], house[i - 1][2]) + r;
		house[i][1] = min(house[i - 1][0], house[i - 1][2]) + g;
		house[i][2] = min(house[i - 1][0], house[i - 1][1]) + b;
	}
 
	cout << min(house[n][0], min(house[n][1], house[n][2]));
	return 0;
}

 

i번째 집을 빨강, 초록, 파랑으로 칠했을 때의 비용의 최소값을 구하기 위해

배열 house[1001][3]을 선언한다.

 

house[i][0]에는 i번째 집을 빨강색으로 칠할 때의 최소비용,

house[i][1]에는 i번째 집을 초록색으로 칠할 때의 최소비용,

house[i][2]에는 i번째 집을 파랑색으로 칠할 때의 최소비용을 저장한다.

 

house[i]가 빨강색으로 칠해지기 위해서는 이전 집이 초록색이거나 파란색이어야하고,

파란색으로 칠해지기 위해서는 이전 집이 빨강색이거나 초록색이어야하고,

초록색으로 칠해지기 위해서는 이전 집이 빨강색이거나 파란색이어야한다.