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

문제 설명

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

1149번: RGB거리

 

해결 방법

 

두번째 집부터 마지막 집까지 살펴보자.

 

house[1][0] += min(house[0][1], house[0][2]);

두번째 집을 빨강으로 칠하는 비용 += 첫번째 집을 칠할 초록 혹은 파랑 중 더 저렴한 비용.

house[1][1] += min(house[0][0], house[0][2]);

두번째 집을 초록으로 칠하는 비용 += 첫번째 집을 칠할 빨강 혹은 파랑 중 더 저렴한 비용.
house[1][2] += min(house[0][0], house[0][1]);

두번째 집을 파랑으로 칠하는 비용 += 첫번째 집을 칠할 빨강 혹은 초록 중 더 저렴한 비용.

 

마지막 집까지 반복한 후

가장 숫자가 작은값을 결과로 보낸다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int min(int a, int b) 
{
	if (a < b)return a;
	return b;
}

int main()
{

	//INPUT
	int n; cin >> n;
	vector<vector<int>>house(n, (vector<int>(3,0)));

	for (int i = 0; i < n; i++)
	{	cin >> house[i][0] >> house[i][1] >> house[i][2];	}

	//SEARCH
	for (int i = 1; i < n; i++)
	{
		house[i][0] += min(house[i - 1][1], house[i - 1][2]);
		house[i][1] += min(house[i - 1][0], house[i - 1][2]);
		house[i][2] += min(house[i - 1][0], house[i - 1][1]);
	}

	
	int result = min(house[n-1][0], house[n-1][1]);
	result= min(result, house[n-1][2]);

	cout << result;

}