[ C++ 백준 1149 ] RGB거리

https://www.acmicpc.net/submit/1149/77958078

 

DP 복습 겸 한 번 풀어보았다.

struct를 써서 풀어보고 싶어서 이런 식으로 코드를 짰는데, 구조나 속도면에서 좋은지는 잘 모르겠다.

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

struct RGB
{

public:
	RGB() : R(0), G(0), B(0) { }
	RGB(int r, int g, int b) : R(r), G(g), B(b) {}

public:
	int R;
	int G;
	int B;

};

int hCount;
vector<RGB> hColorCostInfos;
int DP[3][1001];
// 색, 몇 번째 집

int main()
{

	cin >> hCount;

	for (int i = 0; i < hCount; ++i)
	{

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

		hColorCostInfos.push_back({ R, G, B });

	}

	DP[0][0] = hColorCostInfos[0].R;
	DP[1][0] = hColorCostInfos[0].G;
	DP[2][0] = hColorCostInfos[0].B;

	for (int i = 1; i < hCount; ++i)
	{
		DP[0][i] = hColorCostInfos[i].R + min(DP[1][i - 1], DP[2][i - 1]);
		DP[1][i] = hColorCostInfos[i].G + min(DP[0][i - 1], DP[2][i - 1]);
		DP[2][i] = hColorCostInfos[i].B + min(DP[1][i - 1], DP[0][i - 1]);

	}

	int lastIndex = hCount - 1;
	int answer = min(DP[0][lastIndex], min(DP[1][lastIndex], DP[2][lastIndex]));
	cout << answer;
}

 

DP를 사용해 이 컬러값의 집을 구할 때 최소값을 계속해 계산해나가 최종적으로 마지막 집에서 제일 비용이 적은 가격을 정하도록 짰다.