백준 17404 RGB거리 2

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

 그냥 RGB거리랑 다른 점은 첫 번째랑 마지막 번째도 이어져 있다고 가정하는 것인데 내가 알고리즘 초보라 푸는데 시간이 너무 오래 걸렸다... 메모리는 굳이 1000개짜리를 사용하지 않아도 풀이가 가능하다. 그냥 RGB 거리를 풀었다고 생각하고 추가된 아이디어는, 메모이제이션으로 사용한 배열 rgb[a][b] 은 첫 번째 집은 a 로 칠하고, 마지막 번째 집은 b 로 칠하는 최소 비용이다. 아이디어 자체는 쉬운데 경계값 처리가 조금 힘들다. b 마지막 인덱스가 아니라면 a, b 위치가 동일한 값이 들어갈 수 있다.

 위 코드는 오른쪽이 하드코딩, 왼쪽이 for 문으로 바꾼 것이다. 욕심을 좀 과하게 부려서 오히려 코드가 늘어나는 상황에서도 모두 for 문으로 바꿨다. 오른쪽 코드는 개선의 여지가 보이고 왼쪽 코드는 가독성이 안 좋으니 실제 코드라면 적절히 섞어서 사용하기를...

#include <iostream>
#include <algorithm>

using namespace std;

int rgb[3][3];
int n;

int main() {
    int in[3];

    cin >> n;

    cin >> rgb[0][0] >> rgb[1][1] >> rgb[2][2];

    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (i != j) rgb[i][j] = 1000;

    for (int i = 1; i < n - 1; ++i) {
        scanf("%d %d %d", &in[0], &in[1], &in[2]);

        for (int j = 0; j < 3; ++j) {
            int x[3];
            for (int k = 0; k < 3; ++k) {
                x[k] = 1000 * 1000;
                for (int h = 0; h < 3; ++h) 
                    if(k != h) 
                        x[k] = min(x[k], in[k] + rgb[j][h]);
            }

            for (int k = 0; k < 3; ++k) rgb[j][k] = x[k];
        }
    }

    int m = 1000 * 1000;

    scanf("%d %d %d", &in[0], &in[1], &in[2]);
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (i != k && j != k) m = min(m, in[k] + rgb[i][j]);
            }
        }
    }

    cout << m;

    return 0;
}