1149 -RGB 거리

	#include <iostream>
	using namespace std;
	const int MAX = 1000;
	int N;
	int d[4][MAX + 1];
	int house[4][MAX + 1]; // [1] : red, [2] : green, [3] : blue
	int main(void)
	{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N;
	for (int i = 1; i <= N; i++) {
	cin >> house[1][i] >> house[2][i] >> house[3][i];
	}
	for (int i = 1; i <= N; i++) {
	d[1][i] = min(d[2][i - 1], d[3][i - 1]) + house[1][i];
	d[2][i] = min(d[1][i - 1], d[3][i - 1]) + house[2][i];
	d[3][i] = min(d[2][i - 1], d[1][i - 1]) + house[3][i];
	}
	cout << min(d[3][N], min(d[1][N], d[2][N])) << '\n';
	return 0;
	}

view raw 1149.cpp hosted with ❤ by GitHub

문제 :

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

 

다시 풀어보니 쉬운 문제였습니다.

​

크게 3가지의 값으로 나눌 수 있습니다. N번째집이 마지막집이라고 할 때

1) d[1][N] : N번째 집의 색이 레드이고, 이 값이 최솟값일때

2) d[2][N] : N번째 집의 색이 그린이고, 이 값이 최솟값일때

3) d[3][N] : N번째 집의 색이 블루이고, 이 값이 최솟값일때

​

위 3가지처럼 나누고 바텀업 방식으로 해결할 수 있는 문제였습니다.