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

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

 

먼저 모든 집의 RGB에 해당하는 비용 값을 벡터를 통해 입력받고 n-1까지의 합벡터를 채워주면 되는데 이때 RGB를 더할 때 문제에서 각 집을 칠할 때 이전 집과 같은 색을 사용할 수 없으므로, 이 조건을 만족하며 비용을 최소화하는 선택만을 하도록 하여 자신을 제외한 이전에 계산된 비용중에서 최소값과 자신의 비용을 더한 것이 현재 위치의 합 배열이 값으로 계산해주면 된다.

 

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<vector<int>> cost(n, vector<int>(3));
	vector<vector<int>> dp(n, vector<int>(3));

	//RGB입력받기
	for (int i = 0; i < n; i++)
	{
		cin >> cost[i][0] >> cost[i][1] >> cost[i][2];
	}

	// 첫 번째 집 초기화
	dp[0][0] = cost[0][0];
	dp[0][1] = cost[0][1];
	dp[0][2] = cost[0][2];

	//미리 모든 경우의수 계산
	for (int i = 1; i < n; i++)
	{
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
		dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
	}

	int result = min({ dp[n - 1][0], dp[n - 1][1], dp[n - 1][2] });
	cout << result << endl;

	return 0;
}