[백준1149, Java] RGB거리

문제

www.acmicpc.net/problem/1149

1149번: RGB거리

풀이

minPrice[n][c] 를 n개의 집을 색칠할때 끝의 집이 c(red, green, blue)인 경우 비용의 최소값으로 정의했다. 따라서 minPrice[n][R] 은 min(minPrice[n-1][G] , minPrice[n-1][B]) + price[n][R]이 된다. 최종 답은 min(minPrice[n][R],minPrice[n][G],minPrice[n][B])이다

 

 

소스

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    public static int[][] minPrices;
    public static int[][] prices;
    public static int RED = 0;
    public static int GREEN = 1;
    public static int BLUE = 2;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int  N = Integer.parseInt(br.readLine());
        minPrices = new int[N+1][3];
        prices = new int[N+1][3];

        for(int n = 1; n<=N; n++){
            st = new StringTokenizer(br.readLine()," ");
            prices[n][RED] = Integer.parseInt(st.nextToken());
            prices[n][GREEN] = Integer.parseInt(st.nextToken());
            prices[n][BLUE] = Integer.parseInt(st.nextToken());
        }

        for(int n = 1; n<=N; n++){
            if(n ==1 ){
                minPrices[n][RED] = prices[n][RED];
                minPrices[n][GREEN] = prices[n][GREEN];
                minPrices[n][BLUE] = prices[n][BLUE];
            }
            else{
                minPrices[n][RED] = Math.min(minPrices[n-1][GREEN] ,minPrices[n-1][BLUE] )+ prices[n][RED];
                minPrices[n][GREEN] = Math.min(minPrices[n-1][RED] ,minPrices[n-1][BLUE] )+ prices[n][GREEN];
                minPrices[n][BLUE] = Math.min(minPrices[n-1][RED] ,minPrices[n-1][GREEN] )+ prices[n][BLUE];
            }
        }

        int minPrice = minPrices[N][RED];
        for(int color =1 ;color< 3; color++){
            if(minPrice> minPrices[N][color]){
                minPrice = minPrices[N][color];
            }
        }

        bw.write(String.valueOf(minPrice));
        bw.flush();

        br.close();
        bw.close();




    }
}