[백준/BOJ] 1149 RGB거리 - JAVA - 실버1

[백준/BOJ] 1149 RGB거리 - JAVA - 실버1

문제

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

문제 분석

조건

• N개의 집이 일렬로 있다.
• 각 집은 빨강, 초록, 파랑 중 하나로 칠해야 한다.
• 서로 인접한 두 집은 같은 색으로 칠할 수 없다.
• 모든 집을 칠하는 비용이 주어질 때, 전체 최소 비용을 구하는 문제이다.

풀이방법

• i번째 집을 칠할 때는, 바로 앞 집과 같은 색을 사용할 수 없다는 제약이 존재한다.
• 따라서 i번째 집을 빨강으로 칠한다면, i-1번째 집은 초록이나 파랑으로 칠해야 한다.
• 이 원리를 바탕으로, 현재 집을 어떤 색으로 칠할지를 결정할 때는 이전 집에서 가능한 두 가지 색 중 더 적은 비용을 선택하여 누적해나가는 방식으로 최소 비용을 구할 수 있다.
• 점화식에 따라 각 집을 어떤 색으로 칠할지를 결정하면서, 조건을 만족하는 누적 최소 비용을 구해나간다.
• 마지막 집까지 계산을 마친 후, 세 가지 색 중 최소값을 선택하면 전체 집을 칠하는 데 드는 최소 비용을 얻을 수 있다.
• 이를 기반으로 dp[color][i]는 i번째 집을 color로 칠했을 때의 누적 최소 비용을 의미하며, 점화식은 다음과 같이 정의된다.

dp[RED][i] = min(dp[GREEN][i-1], dp[BLUE][i-1]) + cost[RED][i] 
dp[GREEN][i] = min(dp[RED][i-1], dp[BLUE][i-1]) + cost[GREEN][i] 
dp[BLUE][i] = min(dp[RED][i-1], dp[GREEN][i-1]) + cost[BLUE][i]

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[][] cost = new int[3][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int color = 0; color < 3; color++) {
                cost[color][i] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] dp = new int[3][N];
        int red = 0;
        int green = 1;
        int blue = 2;
        dp[red][0] = cost[red][0];
        dp[green][0] = cost[green][0];
        dp[blue][0] = cost[blue][0];
        for (int i = 1; i < N; i++) {
            dp[red][i] = Math.min(dp[green][i - 1], dp[blue][i - 1]) + cost[red][i];
            dp[green][i] = Math.min(dp[red][i - 1], dp[blue][i - 1]) + cost[green][i];
            dp[blue][i] = Math.min(dp[green][i - 1], dp[red][i - 1]) + cost[blue][i];
        }
        System.out.println(Math.min(Math.min(dp[red][N - 1], dp[blue][N - 1]), dp[green][N - 1]));
    }
}

결과