[Java] 백준 1149 RGB 거리

 

문제

집 N개가 있다.

각각의 집은 빨강, 초록, 파랑으로 칠할 수 있다.

각각의 집에 각각의 색깔을 칠하는 가격은 다르다.

또한 인접한 집의 색깔은 같아선 안된다.

위의 규칙을 모두 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해라

 

 

풀이

N번째 집을 칠해야 하는 상황이라고 생각해보자.

1) N번째 집을 빨간색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다.

- N-1번째 집이 초록색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용

- N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 + N번째 집 빨간색으로 칠하는 비용

 

2) N번째 집을 초록색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다.

- N-1번째 집이 파란색으로 칠할 때 비용의 최솟값 + N번째 집 초록색으로 칠하는 비용

- N-1번째 집이 빨간색으로 칠할 때 비용의 최솟값 + N번째 집 초록색으로 칠하는 비용

 

3) N번째 집을 파란색으로 칠할 때 비용의 최솟값은? 아래의 2가지 경우 중 작은 값이다.

- N-1번째 집이 빨간색으로 칠할 때 비용의 최솟값 + N번째 집 파란색으로 칠하는 비용

- N-1번째 집이 초록색으로 칠할 때 비용의 최솟값 + N번째 집 파란색으로 칠하는 비용

 

이것을 점화식으로 나타내면 다음과 같이 나타낼 수 있다.

- dp[N][red] = cost[N][red] + Math.min(dp[N-1][blue], dp[N-1][green]) 

- dp[N][green] = cost[N][green] + Math.min(dp[N-1][red], dp[N-1][blue])

- dp[N][blue] = cost[N][blue] + Math.min(dp[N-1][red], dp[N-1][green])

 

 

 

코드

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

public class Main {

    // 일반 dp
    static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        for (int i = 1; i < N; i++) {
            dp[i][0] += Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] += Math.min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] += Math.min(dp[i - 1][0], dp[i - 1][1]);
        }

        System.out.println(Arrays.stream(dp[N - 1]).min().getAsInt());
    }

    // 슬라이딩 윈도우
    static void solution2() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

        int[][] dp = new int[2][3];
        dp[0][0] = costs[0][0]; dp[0][1] = costs[0][1]; dp[0][2] = costs[0][2];
        for (int i = 1; i < N; i++) {
            dp[i % 2][0] = costs[i][0] + Math.min(dp[(i + 1) % 2][1], dp[(i + 1) % 2][2]);
            dp[i % 2][1] = costs[i][1] + Math.min(dp[(i + 1) % 2][0], dp[(i + 1) % 2][2]);
            dp[i % 2][2] = costs[i][2] + Math.min(dp[(i + 1) % 2][0], dp[(i + 1) % 2][1]);
        }

        System.out.println(Arrays.stream(dp[(N - 1) % 2]).min().getAsInt());
    }

    public static void main(String[] args) throws IOException {
//    	solution();
        solution2();
    }
}