[BOJ] 17404: RGB거리 2

문제 소개

오랜만에 문제 풀이입니다.

2020.03.27 기준,  solved.ac 골드 4티어 문제입니다.

 

먼저, 문제를 풀 수 있는 아이디어부터 설명하고

코드를 설명하겠습니다.

 

 

문제 링크

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

17404번: RGB거리 2

아이디어

처음에는 어떻게 접근할까 잘 생각이 안나서 조금 다른분들 풀이를 찾아봤습니다.

근데, 찾아보다가 그냥 3차원인듯 3차원 아닌 DP로 풀면 되잖아! 하면서 문제를 해결했습니다.

 

DP table 정의는 다음과 같이 했습니다.

D[i][j][start]: 0번째 집은 start 색상으로 칠하고나서 i-1번째 집까지 어떻게든 색을 칠했고, i번째 집에 j번째 색상을 칠하려할 때의 최소비용

 

구현에 대한 자세한 것은 코드로 보면 될 것 같습니다.

코드

#include <iostream>
#include <algorithm>
#define Mx 123456789
using namespace std;
int N;
int D[1100][5][5];
int ar[1100][5];
int main() {
    //input
    cin >> N;
    for(int y = 0; y < N; y++) {
        for(int x = 0; x<3; x++) cin >> ar[y][x];
    }
    // initialization
    for(int y=0; y<N;y++) {
        for(int x=0; x<3; x++) {
            for(int z =0; z<3; z++) D[y][x][z] = Mx;
        }
    }
    for(int x=0; x<3; x++) {
        D[0][x][x] = ar[0][x];
    }
    // fill DP table
    for(int y=1; y<N; y++) {
        for(int x = 0; x < 3; x++) {
            for(int start = 0; start < 3; start++) {
                if(y == N-1) {
                    if(x != start) {
                        D[y][x][start] = min(D[y-1][(x+1)%3][start] , D[y-1][(x+2)%3][start]) + ar[y][x];
                    }
                }
                else {
                    D[y][x][start] = min(D[y-1][(x+1)%3][start] , D[y-1][(x+2)%3][start]) + ar[y][x];
                }
            }
        }
    }

    // find min answer
    int ans = Mx;
    for(int x = 0; x < 3; x ++) {
        for(int start = 0; start < 3; start++) {
            ans = min(ans,D[N-1][x][start]);
        }
    }
    cout<<ans;

}

Rmx