문제 소개 📌

문제 링크 📢

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

문제 풀이 📝

문제에서 i번째 집과 i-1번째 집은 색이 달라야 한다고 주어졌다. 또한 모든 집을 칠하는데 드는 비용의 최솟값을 구해야하므로 i번째 집까지의 최소 비용을 dp배열에 갱신하면서 진행해 N번째 집의 최소 비용을 구할 것이다.
하지만 이 때 처음에 어떤 집을 칠했는 지는 3가지 경우의 수(R,G,B)를 모두 고려해야하므로 dp배열을 dp[N][3]과 같이 선언하여 최솟값을 갱신하면 된다!
그 후 현재 색깔을 제외한 나머지 두 색깔 중 최솟값을 현재 dp에 갱신하며 N까지 진행하면 AC를 받을 수 있다.

코드

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

using namespace std;


int main()
{
	int RGB[1001][3];
	int dp[1001][3];
	int N;
	int R, G, B;
	
	cin >> N;
	dp[0][0] = 0;
	dp[0][1] = 0;
	dp[0][2] = 0;
	for (int i = 1; i < N+1; i++)
	{
		cin >> R >> G >> B;

		dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + R;
		dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + G;
		dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + B;
	}
	cout << min(min(dp[N][0], dp[N][1]), dp[N][2]);
	return 0;
}