백준 1149 RGB거리

문제

문제링크: https://www.acmicpc.net/problem/1149

풀이전략

1. 인접한 두 집의 색은 달라야한다.
2. 메모이제이션을 하되, 현재 집의 색과 위치에 따라 메모이제이션을 해야한다.

코드

#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로 메모이제이션을 할 배열을 만들어 해결하였다. 앞으로 자주 쓸 테크닉일지도 모르니 잘 알아두고 가야겠다.