RGB거리(백준)

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

using namespace std;
int house[1001][3];

bool cmp(int a, int b)
{
	return a < b;
}

int main()
{
	int N;
	cin >> N;
	int cost[3];
	house[0][0] = 0;
	house[0][1] = 0;
	house[0][2] = 0;

	for (int i = 1; i <= N; i++)
	{
		cin >> cost[0] >> cost[1] >> cost[2];
		house[i][0] = min(house[i - 1][1], house[i - 1][2]) + cost[0];
		house[i][1] = min(house[i - 1][0], house[i - 1][2]) + cost[1];
		house[i][2] = min(house[i - 1][0], house[i - 1][1]) + cost[2];
	}


	int iTemp1 = house[N][0];
	int iTemp2 = house[N][1];
	int iTemp3 = house[N][2];

	vector<int> vTemp;
	vTemp.emplace_back(iTemp1);
	vTemp.emplace_back(iTemp2);
	vTemp.emplace_back(iTemp3);

	sort(vTemp.begin(), vTemp.end(), cmp);

	cout<< vTemp[0];
	return 0;
}

[못풀었음]
1. min을 이용하여 최솟값 구하는것(둘중 한개)
2. DP를 사용하는데 이유는 n번째의 가격은 n-1번째의 가격들을 토대로 구해지기 때문임.

Dp[n]번째 가격은 같은줄 말고 다른줄 중에서 제일 작은 값 + cost[n]의 값을 구한다.
3.2에서 구한 값 3개중 제일 작은 값을 반환한다.

좋은 웹페이지 즐겨찾기