백준 1149 : RGB 거리

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

1. 접근

• 최솟값을 구하기위해 경로를 탐색한다고 생각하여 처음에는 DFS로 접근했다.
  => 그러나 시간초과...
• 경로탐색의 경우, n번째의 결과에 1~n-1까지의 모든 경우의수가 영향을 끼치지만, 이 문제는 오직 n-1번째의 결과만이 n번째 결과에 영향을 준다
  => DP 로 접근해야 한다
• 따라서 DP 배열을 설정하고, DP에서 n-1번째에 선택한 RGB값이 아닌 값들끼리의 최솟값을 구하도록 했다.
• 메모리를 아끼기 위해 입력을 받으면서 바로 DP 값을 계산하도록 했다.

2. 나의 풀이

#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][3];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int r, g, b;
		cin >> r >> g >> b;
		if (i > 0) {
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r;
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g;
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b;
		}
		else {
			dp[i][0] = r;
			dp[i][1] = g;
			dp[i][2] = b;
		}
		//cout << "dp " << i << "번째 : " << dp[i][0] << "," << dp[i][1] << "," << dp[i][2] << "\n";
	}

	if (dp[n - 1][0] <= dp[n - 1][1]) {
		if (dp[n - 1][0] <= dp[n - 1][2])	cout << dp[n - 1][0] << "\n";
		else cout << dp[n - 1][2] << "\n";
	}
	else {
		if (dp[n - 1][1] <= dp[n - 1][2])	cout << dp[n - 1][1] << "\n";
		else cout << dp[n - 1][2] << "\n";
	}
	return 0;
}