[백준] 1149 RGB거리 (JAVA)

풀이

 이 문제는 정석적인 DP라고 볼수있겠다. 심지어 색도 3개이고 집의 개수도 적어서 시간 걱정 역시 안해도 된다. 문제에서 조건을 까다롭게 주었는게 결국은 인접한 집들끼리는 색이 겹처서는 안된다는 말이다.

 

 알고리즘의 개요는 입력 받아 저장하는 2차원 int형 배열인 street와 dp를 만들면된다. 그러고 나서 dp의 첫번째 줄은 초기화를 해주고 그 다음은 겹치지 않는 색들끼리(dp) 비교해서 그 중 작은 값과 현재집의 특정색상과 더해서 저장

DP를 끝까지 수행해주면 dp[N-1]중에서 가장작은값을 출력.

 

코드 

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

class Main {

    public static int N;
    public static int[][] street;
    public static int[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        street = new int[N][3];
        dp = new int[N][3];

        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<3; j++){
                street[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        findMin();
    }

    public static void findMin() {
        dp[0][0] = street[0][0];
        dp[0][1] = street[0][1];
        dp[0][2] = street[0][2];

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                switch (j) {
                    case 0:
                        dp[i][0] = street[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
                        break;

                    case 1:
                        dp[i][1] = street[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
                        break;

                    case 2:
                        dp[i][2] = street[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
                        break;
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for(int i=0; i<3; i++){
            if(min > dp[N-1][i])
                min = dp[N-1][i];
        }
        System.out.println(min);
    }

}