문제 출처

단계별로 풀어보기 > 동적 계획법 1 > RGB 거리
https://www.acmicpc.net/problem/1149

문제 설명

N개의 집이 있을 때, 각각 집들은 빨강, 초록, 파랑 중 하나의 색으로 해야한다.
각 집마다 색상을 칠하는 가격이 다르고, 하나의 집에 색을 칠하면 그 집의 양 옆은 다른 색이어야할 때, N개의 집에 색을 칠하는 최솟값을 구하라

접근 방법

처음 집들을 빨강, 초록, 파랑이 되는 경우를 입력하고, 이 후, 2번(0 based로 1번) 집의 색을 칠하는 경우를 생각하면, 2번 집이 빨강인 경우, 1번 집은 파랑과 초록, 2번 집이 파랑인 경우 , 1번 집은 빨강과 초록, 2번 집이 초록인 경우, 1번 집은 빨강과 파랑의 경우를 생각한다.

2번 집의 색상에 따라서, 2번과 다른 색상으로 칠한 경우의 1번 집 경우 2가지의 비용을 비교하여 2번 집 색상 가격 + 1번 집 색상 가격( 중 최소)를 해당 경우에 저장한다. 이를 반복하여 마지막에 최솟값을 출력하면 된다.

import java.io.*;
import java.util.StringTokenizer;

public class RGB거리 {

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

        int[][] house = new int[N][3];

        StringTokenizer st = new StringTokenizer(br.readLine());
        house[0][0] = Integer.parseInt(st.nextToken());
        house[0][1] = Integer.parseInt(st.nextToken());
        house[0][2] = Integer.parseInt(st.nextToken());

        for(int i = 1; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<3; j++){
                int curCost = Integer.parseInt(st.nextToken());

                switch(j){
                    case 0 : house[i][0] = Math.min(house[i-1][1] + curCost, house[i-1][2] + curCost);
                    break;
                    case 1 : house[i][1] = Math.min(house[i-1][0] + curCost, house[i-1][2] + curCost);
                    break;
                    case 2:
                        house[i][2] = Math.min(house[i-1][1] + curCost, house[i-1][0] + curCost);
                        break;
                }

            }
        }
        int result = Math.min(house[N-1][0], house[N-1][1]);
        result = Math.min(result, house[N-1][2]);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }

}

Review

import java.io.*;
import java.util.StringTokenizer;

public class RGB거리_review {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int dp[][] = new int[N][3];

        StringTokenizer st = new StringTokenizer(br.readLine());

        dp[0][0] = Integer.parseInt(st.nextToken());
        dp[0][1] = Integer.parseInt(st.nextToken());
        dp[0][2] = Integer.parseInt(st.nextToken());

        for(int i = 1; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j<3; j++){
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
            dp[i][0] = Math.min(dp[i][0] + dp[i-1][1],dp[i][0] + dp[i-1][2]);
            dp[i][1] = Math.min(dp[i][1] + dp[i-1][0],dp[i][1] + dp[i-1][2]);
            dp[i][2] = Math.min(dp[i][2] + dp[i-1][1],dp[i][2] + dp[i-1][0]);
        }
        int result = Math.min(Math.min(dp[N-1][0],dp[N-1][1]),dp[N-1][2]);

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }

}

알게된 점

안 쪽 for문을 이용한 switch case문을 이용했는데, 굳이 그럴 필요 없이 세개를 동시에 해도 될 것 같다.

Review
dp의 방식을 어느정도 이해한 것 같다. 정말 금방 풀었다.

문제푼 흔적

Review