[백준] 1149 RGB거리_Java

 

문제 링크

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

 

 

문제 풀이

1. 1번 집부터 N번 집이 순서대로 있다.
2. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 모든 집을 칠하는 비용의 최솟값을 구해보자.

3. 인접하는 집의 색은 같은 색으로 칠할 수 없다.

 

 

 

 

코드

DP알고리즘을 이용하여, i번째 집을 빨강, 초록, 파랑 색으로 칠할 경우 최소 비용을 구하는 것을 반복하여 N번째 집까지 칠하는 최소 비용을 구한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());

        int[][] dp = new int[n][3];
        StringTokenizer st = new StringTokenizer(bf.readLine());
        for(int i=0; i<3;i++) dp[0][i] = Integer.parseInt(st.nextToken());

        for(int i=1; i<n; i++){
            st = new StringTokenizer(bf.readLine());
            for(int j =0; j<3; j++ ) {
                int temp  = Integer.parseInt(st.nextToken());
                int num =Integer.MAX_VALUE;
                for(int k=0; k<3; k++){
                    if(j==k) continue;
                    num = Math.min(num,dp[i-1][k]+temp);
                }
                dp[i][j]=num;
            }
        }

        int min = Integer.MAX_VALUE;
        for(int i=0; i<3; i++) min = Math.min(min, dp[n-1][i] );
        System.out.println(min);
    }
}

 

 

 

실행 결과