#1149번 RGB거리 (C++)

참고 : https://lmcoa15.tistory.com/2 

#include <iostream>
#include <algorithm> 
using namespace std;

int T;
int RGB[1001][3] = {0};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> T;

    for(int i=1; i<=T; i++){
        cin >> RGB[i][0];
        cin >> RGB[i][1];
        cin >> RGB[i][2];

        RGB[i][0] += min(RGB[i-1][1], RGB[i-1][2]);
        RGB[i][1] += min(RGB[i-1][0], RGB[i-1][2]);
        RGB[i][2] += min(RGB[i-1][0], RGB[i-1][1]);
    }

    cout << min(RGB[T][0], min(RGB[T][1], RGB[T][2]));

    return 0;
}

백트래킹을 생각했다가 틀려버린 문제.

아직 백트래킹이 익숙하지 않은 탓에 단번에 틀려버렸고, 

분명 더 좋은 해결책이 있을거라는 생각에 검색하다가 좋은 해설을 발견하였다. 

 

1. [0][i]는 0으로 입력하고, [1][i]부터 시작한다. 

2. 입력값 + 이전에 받은 값 중 적은 값 (본인의 컬러와는 다름) = 누적 되는 총합 

3. 집의 갯수만큼 합산이 끝나면, RGB로 각각 하나씩 시작해서 누적 된 총합 3개 중 가장 적을 것을 선택

 

짧고 굵은 알고리즘 문제였다.