[연속 dp] 1149 RGB 거리

1149 RGB 거리

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 1149 RGB 거리
const int MAX = 1000;
int n;
int A[MAX + 1][3];
int cache[MAX + 1][3];

int min(int a, int b){
	return a > b ? b : a;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> n;
	
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			cin >> A[i][j];
			if(i == 1) cache[i][j] = A[i][j];
		}
	}
	
	
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			cache[i][j] = min(cache[i - 1][ (j+1) % 3], cache[i - 1][ (j+2) % 3]) + A[i][j];
		}
	}
	
	cout << min( min(cache[n][0], cache[n][1]), cache[n][2]) << '\n';
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

0. 브루트 포스는 N 이 1000 이하 이므로 불가능하다. 3^1000 > 1억

1. 다이나믹 프로그래밍 + 연속성과 관련된 문제이다. (이전에 풀었던 문제들과 맥락이 비슷)

2. 3가지의 색깔이 서로 연속하면 안되는 것을 배열로써 판별해야 하므로,

cache[i][j] : 1 ~ i 번째 집까지, i 번째 집을 j색으로 칠했을 때, 비용의 최솟값을 저장하는 배열

로 정의한다.

3. 그러면,

cache[i][j] = min(cache[i - 1][ (j+1) % 3], cache[i - 1][ (j+2) % 3]) + A[i][j]

임을 도출해낼 수 있다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점