(c++)1149_RGB거리 💔💚💙

😀 백준 RGB거리 (c++)

https://www.acmicpc.net/problem/1149

처음에는 재귀함수를 사용해서 풀 수 있을 것이라고 생각해서 재귀로 문제를 풀어보았다.

하지만 시간초과가 발생하였고 질문을 보다보니 DP를 사용해서 푸는 방법이 있다는 것을 알게되었다.

내 로직을 간단히 설명하면 다음과 같다.

• 1번째(시작)에 해당하는 각 색(R,G,B)의 가격을 minCosts라는 배열에 넣는다.
• i = 2 .. N 까지 각 색(R,G,B)을 선택했을 때 구할 수 있는 최소 가격을 minCosts[i]에 넣는다.
  --> R일 경우 G,B만 / G일 경우 R,B만 / B일 경우 R,G만 선택 가능
  --> 선택가능한 색 중 가격이 작은 색을 선택하면 그것이 최선의 선택이 된다.
• minCosts[N]의 값이 구할 수 있는 최소값이 된다.

---

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;

int N;
vector<vector<int>> costs; //가격
vector<vector<int>> minCosts(1001, {INT_MAX,INT_MAX,INT_MAX}); //각 색칠별 최소가격

//해당 index에서 각 색을 선택했을 때 나올수 있는 최소 가격을 구함
void getCosts(int index) {
	for (int i = 0; i < 3; i++) { 
		vector<int> canCosts;
		for (int k = 0; k < 3; k++) {
			if (k != i) {
				canCosts.push_back(minCosts[index-1][k]);
			}
		}
		int selected = min(canCosts[0], canCosts[1]);
		int nowCost = selected + costs[index][i];
		minCosts[index][i] = min(minCosts[index][i], nowCost);
	}
}

int main() {
	cin >> N; //입력
	costs.push_back({});
	for (int i = 0; i < N; i++) {
		int c1, c2, c3; cin >> c1 >> c2 >> c3;
		costs.push_back({ c1,c2,c3 });
	}
	minCosts[1] = costs[1]; //시작
	for (int i = 2; i <= N; i++) {
		getCosts(i);
	}
	int answer = min(minCosts[N][0], minCosts[N][1]);
	answer = min(answer, minCosts[N][2]);
	cout << answer << endl;
	return 0;
}