RGB 거리2

문제 링크

이전 RGB거리문제와 동일한 문제지만 첫집과 마지막집도 같은 규칙을 지켜야 한다는 제약이 추가된 문제다. 이 문제처럼 고리형 구조를 가진 DP문제를 환형 DP라고 개인적으로 부르고 있다. 환형 DP는 보통 첫 위치에 가능한 경우를 모두 대입해서 푼다. 이 문제에 경우 가능한 색은 3가지이므로 3가지 색을 모두 대입하고 마지막 집을 검사할 때 첫 집과의 추가 비교를 통해 첫 집이 특정 색일 때의 답 3가지를 구할 수 있다. 이렇게 나온 3가지 답을 다시 비교해서 최종 답을 구하는 것이 환형 문제를 푸는 템플릿이라고 할 수 있다.

발상

환형 문제 풀이에 대한 발상은 순수 직관이다. (난 프로그래머스 도둑 문제 풀다가 스스로(중요) 떠올렸다.) 점화식에 대한 발상은 이전 문제를 참고하길 바란다.

점화식

$$n_{i,c}=\min (n_{i-1,c+1\mathrm{mod}3},n_{i-1,c+2\mathrm{mod}3})+cos{t}_{i,c}$$

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ull = long long;
int main()
{
	int n; cin >> n; vector<vector<int>> arr(n + 1, vector<int>(3)), dp;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
	}
	int mn = 21e8;
	for (int k = 0; k < 3; k++) { // 첫집 색
		dp = vector<vector<int>>(n + 1, vector<int>(3, 21e8));
		dp[1][k] = arr[1][k]; // 첫집 색은 무조건 k
		for (int i = 2; i <= n; i++) { // 현재 집 인덱스
			for (int j = 0; j < 3; j++) { // 비용을 구할 현재 집 색
				for (int l = 0; l < 3; l++) { // 비용을 구할 이전 집 색
					if (i == n && j == k) continue; // 마지막이면 첫집과도 비교해 같은 색이면 탐색 생략
					if (j == l) continue; // 현재 집과 같은 색의 이전 집은 탐색 생략
					dp[i][j] = dp[i - 1][l] < dp[i][j] ? dp[i - 1][l] : dp[i][j]; // 가능한 이전 비용 중 최소 비용 선택
				}
				dp[i][j] += arr[i][j]; // 현재 집 도색 비용 추가
			}
		}
		int s = min({ dp[n][0], dp[n][1], dp[n][2] }); // 마지막 집 도색 비용 중 최소 비용 선택
		mn = mn < s ? mn : s; // 모든 k에 대해 최소 비용 선택
	}
	cout << mn;
	return 0;
}