문제링크: https://www.acmicpc.net/problem/1149
#include<bits/stdc++.h>
using namespace std;
const int RED = 0;
const int GREEN = 1;
const int BLUE = 2;
int N;
// 위치에 따른 색을 저장하는 배열
int a[3][1001];
// 해당 색과 위치에따라 메모이제이션을 하는 배열
int cache[3][1001];
int findRGB(int n, int currentColor){
// 기저사례
if(n > N) return 0;
int&ret = cache[currentColor][n];
if(ret != -1) return ret;
// 어차피 ret의 값은 바뀔거기에 최대값을 주기
ret = 987654321;
for(int i=0; i<3; i++){
if(i!= currentColor){
// RED, GREEN, BLUE 색에 따라 어떻게 값을 넣어야하는지에 대한 최솟값을 구하기
// currentColor는 이전 재귀에서 보내준 현재위치
// currentColor와 i 가 같아지면 인접한 두칸의 같은 색이되므로 이를 피해주기
ret = min(ret, a[currentColor][n]+findRGB(n+1, i));
}
}
return ret;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
memset(a, -1, sizeof(a));
memset(cache, -1, sizeof(cache));
cin >> N;
for(int i=1; i<=N; i++){
cin >> a[RED][i] >> a[GREEN][i] >> a[BLUE][i];
}
cout << min(findRGB(1, RED), min(findRGB(1, GREEN), findRGB(1, BLUE))) << endl;;
return 0;
}
2D로 메모이제이션을 할 배열을 만들어 해결하였다. 앞으로 자주 쓸 테크닉일지도 모르니 잘 알아두고 가야겠다.