[문제 풀이] 백준 Num 17404 RGB거리2

오늘의 문제 : https://www.acmicpc.net/problem/17404

 

문제

양 옆 집의 색이 겹치지 않게 칠하는 최소비용을 구해야 합니다. (단, 1번 집과 N번 집은 옆에 있다고 가정) 

 

풀이

문제를 조금 간단하게 생각하면 풀이에 쉽게 도달할 수 있습니다.

 

양 옆집이라서 양 방향으로 탐색을 진행하지 않고, 1번 집부터 2번, 3번.. 한 방향으로 나아가도 문제의 조건을 만족할 수 있습니다. 

 

그러다 N번째 집에서는 이전 집 색 + 처음 집 색을 통해 색을 구분하고 값을 구하면 됩니다. 

 

재미있는 점은 DP를 적용하여 값을 저장할 때 1번 집의 색 마다 다른 값을 저장해줘야 합니다. 그 이유는 1번 집과 마지막 집의 색이 달라야 하기 때문입니다. 그러다 보면 1번 집의 색에 따라서 특정 집의 같은 색을 칠하기 위한 비용이 달라지기 때문입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Num17404RGB거리2 {
    static int n;
    static final int R = 0,G=1,B=2;
    static int[][] costs, dp;
    static int[] vis;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        costs = new int[n][3];
        vis = new int[n];
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int index = R;
            while(st.hasMoreTokens()){
                costs[i][index] = Integer.parseInt(st.nextToken());
                index++;
            }

        }
        int ans = Integer.MAX_VALUE;
        for(int i=0;i<3;i++){
            vis[0] = i;
            dp = new int[n][3];
            for(int j=0;j<n;j++){
                Arrays.fill(dp[j],-1);
            }
            ans = Math.min(DFS(0,i),ans);
        }
        System.out.println(ans);
    }
    public static int DFS(int now,int color){
        if(dp[now][color] != -1 ) return dp[now][color];
        if(now == n-1){
            return dp[now][color] = costs[now][color];
        }
        int cost = Integer.MAX_VALUE;

        for(int i=0;i<3;i++){
            if(i==color) continue;
            if(now == n-2){
                if(vis[0] == i) continue;
                cost = Math.min(costs[now][color] + DFS(now+1,i),cost);
            }else{
                vis[now+1] = i;
                cost = Math.min(costs[now][color] + DFS(now+1,i),cost);
            }
        }
        return dp[now][color] = cost;
    }
}