[BOJ]1149 - RGB 거리

1149

전혀 풀이를 생각하지 못해서 풀이를 찾아봤는데 2차원 배열로 모든 경우의 수를 기록한다. 그저 감탄.

난 전혀 DP하고 있지 않아..

아이디어 생각하기가 힘든 것 같다. 풀다 보면 나아지겠지?

해설 코드

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char** argv)
{
	cin.tie(NULL);
	cout.tie(NULL);
	std::ios::sync_with_stdio(false);

	int N;

	cin >> N;

	vector<vector<int>> vec;

	for (int i = 0; i < N; i++)
	{
		int color[3] = {0,0,0};

		cin >> color[0] >> color[1] >> color[2];

		if (i == 0)
		{
			vector<int> value;

			value.push_back(color[0]);
			value.push_back(color[1]);
			value.push_back(color[2]);

			vec.push_back(value);
		}
		else
		{
			vector<int> value;

			int prev = min(vec[i - 1][1], vec[i - 1][2]);
			prev += color[0];

			value.push_back(prev);

			prev = min(vec[i - 1][0], vec[i - 1][2]);
			prev += color[1];

			value.push_back(prev);

			prev = min(vec[i - 1][1], vec[i - 1][0]);
			prev += color[2];

			value.push_back(prev);

			vec.push_back(value);
		}
	}

	int res = min(vec[N - 1][0], vec[N - 1][1]);

	res = min(res, vec[N - 1][2]);

	cout << res;
	
}

참고자료

rgb거리 풀이