🖊️ 문제

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

---

🖊️ 풀이

RGB거리 와 유사한 문제인데,
시작점과 끝점이 동일하면 안된다는 조건이 추가된 문제..

조건 하나만으로 난이도가 두 계단이나 (실1 -> 골4) 뛰다니 ,,, 허헣

그냥 RGB거리는 쉽게 풀었는데,,

시작점과 끝점이 다른 경우의 수는 사실,
r - g
r - b
g - b
g - r
b - r
b - g
이렇게 크게 6가지가 나온다.

냅다 시작점부터 모든 경우의 수 연산하는 것보다,
미리 만들어놓은 DP 점화식에서 내가 원하는 경우(시작점 != 끝점)을 캐치하는게 낫겠다 싶었다.

그래서 전체적으로 루프를 돌건데, 한 번 더 돈다.
각 시작점에 대해서 최소비용을 구하고, 최종 도착지가 시작점과 다르면 (인덱스로 판별) -> result 최솟값 판별.

사실 dp를 3차원배열로 만드니 뭐니 했는데..
생각보다 생각을 쉽게 해야 했다.
DP는 뭐니뭐니해도 쉽게 생각해야 하는게 젤 중요한 것 같다.

#include <iostream>
using namespace std;

int arr[1001][3];
int dp[1001][3];

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

	int n;
	cin >> n;

	int result = 1000 * n;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}

	for (int start = 0; start < 3; start++) {
		for (int j = 0; j < 3; j++) {
			if (j == start) dp[1][j] = arr[1][j];
			else dp[1][j] = 1000 * n;
		}
		for (int i = 2; i <= n; i++) {
			dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
			dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
			dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
		}
		for (int j = 0; j < 3; j++) {
			if (j == start) continue;
			result = min(result, dp[n][j]);
		}
	}

	cout << result << '\n';
}