[C++] 백준 1149번 : RGB거리

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

1149번: RGB거리

---

문제 풀이

 문제의 조건은 앞뒤로 색이 겹치지만 않으면 된다.

따라서, 빨강 → 초록, 파랑 / 초록 → 파랑, 빨강 / 파랑 → 빨강, 초록 이런 식으로 다음에 올 수 있다.

prices 배열은 n번의 계산을 저장한 2차원 배열로, 0에는 빨강, 1은 초록, 2는 파랑을 기준으로 잡는다. 

각 계산 결과는 조건을 성립하므로 결과 중 제일 작은 값만 출력하면 된다.

느낀 점

 처음에는 DFS로 구현하려고 했다. 근데 곰곰히 생각해보니 동적 계획법대로 문제를 풀어야 할 것 같아서 다시 고민했다. 사실 간단한 문제일 수도 있는데 접근법이 잘못돼서 오래 걸린 문제이다.

코드 

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int prices[1001][3];
int cost[3];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> cost[0] >> cost[1] >> cost[2];
		prices[i][0] = min(prices[i - 1][1], prices[i - 1][2]) + cost[0];
		prices[i][1] = min(prices[i - 1][0], prices[i - 1][2]) + cost[1];
		prices[i][2] = min(prices[i - 1][1], prices[i - 1][0]) + cost[2];
	}
	cout << min(prices[n][0], min(prices[n][1], prices[n][2]));
}