백준 1149 : RGB 거리

1. 문제 : https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

2. 문제 접근

• 완전 탐색
  • 최악의 경우에 $3^1000$ -> Time limit으로 사용할 수 없음.
• 백트레킹
  • 입력되는 비용이 오름차순으로 정렬되지 않음.
  • 즉, $N = K$일 때 전체 비용이 $N = K + 1$일 때 전체 비용보다 무조건 작다라고 확신할 수 없어 사용 불가능.
• DP
  • 반복되는 규칙이 존재 : $N = K$에 최솟값은 $N = K - 1$일 때 최솟값에 마지막 칠해진 색과 다른 색 중 최솟값을 더한 값임.
  • 이를 점화식으로 만들 수 있으므로 DP 사용 가능.

 

3. 문제 해결

1. $N = 1$일 때 비용을 저장.
2. $N = K$일 때 칠해야 하는 색과 다른 $N = K - 1$의 비용 중 최솟값과 합하여 저장, 이후 계속해서 반복.
   • $N = K - 1$의 색이 빨강일 때 : 파랑과 초록 중 최솟값을 더함.
   • $N = K - 1$의 색이 파랑일 때 : 빨강과 초록 중 최솟값을 더함.
   • $N = K - 1$의 색이 초록일 때 : 빨강과 파랑 중 최솟값을 더함.
3. $N$일 때 최솟값을 반환하면 해당 값이 구하고자 하는 값.

DP[K][0] = COST[K][0] + min(DP[K - 1][1], DP[K - 1][2]);
DP[K][1] = COST[K][1] + min(DP[K - 1][0], DP[K - 1][2]);
DP[K][2] = COST[K][2] + min(DP[K - 1][0], DP[K - 1][1]);

 

 

4. 코드

#include <iostream>
#include <vector>
using namespace std;

int solution(vector<vector<int>>& costVector)
{
	vector<vector<int>> dp;
	int size = costVector.size();

	// Initialize the cost value of N = 1
	dp.push_back(costVector[0]);

	for (int i = 1; i < size; i++)
	{
		vector<int> temp;

		// if the house's color is Red
		temp.push_back(costVector[i][0] + min(dp[i - 1][1], dp[i - 1][2]));
		// if the house's color is Blue
		temp.push_back(costVector[i][1] + min(dp[i - 1][0], dp[i - 1][2]));
		// if the house's color is Green
		temp.push_back(costVector[i][2] + min(dp[i - 1][0], dp[i - 1][1]));

		dp.push_back(temp);
	}

	return min(dp[size - 1][0], min(dp[size - 1][1], dp[size - 1][2]));
}

int main()
{
	int N;
	vector<vector<int>> costVector;

	cin >> N;

	// Set the initial value
	for (int i = 0; i < N; i++)
	{
		vector<int> temp;
		for (int j = 0; j < 3; j++)
		{
			int cost;
			cin >> cost;
			temp.push_back(cost);
		}
		costVector.push_back(temp);
	}

	cout << solution(costVector);

	return 0;
}