[백준 C++] 1149 RGB거리 - 다이나믹프로그래밍

1149번: RGB거리

#include <iostream>
using namespace std;

int Weight[1001][3];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	int R, G, B;
	cin >> R >> G >> B;

	Weight[1][0] = R;
	Weight[1][1] = G;
	Weight[1][2] = B;
	
	for (int i = 2; i <= N; ++i)
	{
		cin >> R >> G >> B;

		Weight[i][0] = min(Weight[i - 1][1], Weight[i - 1][2]) + R;
		Weight[i][1] = min(Weight[i - 1][0], Weight[i - 1][2]) + G;
		Weight[i][2] = min(Weight[i - 1][0], Weight[i - 1][1]) + B;
	}

	cout << min(min(Weight[N][0], Weight[N][1]), Weight[N][2]);
}

---

 

다이나믹 프로그래밍 유형의 문제입니다.

풀이 방법은

1번 집부터 N번 집까지 순차적으로 색을 칠하는데, 현재 집까지의 최소값을 각 색깔별로 DP 배열에 저장해주는 것입니다.

각 색깔 마다 최소값을 결정하는 요소는 이전 집의 색상이 어떤 것인지의 여부를 판단하면 됩니다.

예를 들어 i번 집을 R로 칠할 때, 1번 집부터 i번 집까지의 최소값은 i-1 집의 G, B 최소값 중 더 작은 값을 더해준 값입니다.

동일한 방식으로 현재 집을 G로 칠할 때, B로 칠할 때의 최소값까지 모두 저장하고,

N번 집까지 DP배열 저장을 모두 마치면 N번 집의 R, G, B DP값 중 최소가 답이 됩니다.