RGB거리 #1149 c++ 풀이

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

1149번: RGB거리

집을 색칠할건데, 비용이 가장 작은 경우를 출력하라는 dp문제이다.

 

경우의 수는 다음과 같다.

이번에 R을 칠할 것이면, 다음에는 GB중 하나를 선택해야한다.

이번에 G을 칠할 것이면, 다음에는 RB중 하나를 선택해야한다.

이번에 B을 칠할 것이면, 다음에는 RG중 하나를 선택해야한다.

3가지 경우의 cost를 전부 세야하는구나를 알았다.

따라서 RGB로 시작하는 각각의 비용을 누적하는 전역변수가 필요할 것이다.

• 따라서, 현재 집의 색을 칠할 때, 이전 집으로 가능한 색들을 확인하고,
• 이전 집들 중, 누적 비용이 가장 적은 색을 선택한 뒤,
• 현재 집까지의 비용을 [현재 집의 비용 + 이전 집까지의 최소 누적 비용] 으로 갱신합니다

#include<iostream>


using namespace std;
int N; 
int houses[1001][3];
int cost[1001][3];

int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 3; j++)
			cin >> houses[i][j];
	}
	cost[0][0] = houses[0][0]; //0번째 것을 고르고 시작했을 때 
	cost[0][1] = houses[0][1]; //1번째 것을 고르고 시작했을 때
	cost[0][2] = houses[0][2]; //2번째 것을 고르고 시작했을 때


	for (int i = 1; i < N; i++) {
		cost[i][0]/*현재의 0번째를 고른 cost는*/ = min(cost[i - 1][1]/*1번째를 고른 cost와 */ + houses[i][0], cost[i - 1][2] + houses[i][0]);

		cost[i][1] = min(cost[i-1][0]+houses[i ][1], cost[i-1][2] +houses[i ][1]);
		cost[i][2] = min(cost[i-1][0]+houses[i ][2], cost[i-1][1]+ houses[i ][2]);
	}
	//for (int i = 0; i < N; i++) {
	//	cout << endl;
	//	cout << cost[i][0] << " " << cost[i][1] <<" " << cost[i][2];
	//	cout << endl;
	//}
	int mi = min(cost[N - 1][0], cost[N - 1][1]);
	mi = min(mi, cost[N - 1][2]);
	cout << mi; 
	return 0;
}