백준_1149_RGB거리

RGB거리 문제

DP를 활용한 문제

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

public class Main {

    final static int Red = 0;
    final static int Green = 1;
    final static int Blue = 2;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

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

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            int r = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            dp[i][Red] = Math.min(dp[i - 1][Green], dp[i - 1][Blue]) + r;
            dp[i][Green] = Math.min(dp[i - 1][Red], dp[i - 1][Blue]) + g;
            dp[i][Blue] = Math.min(dp[i - 1][Red], dp[i - 1][Green]) + b;
        }

        System.out.println(Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2])));

    }

}

1. DP 테이블 초기화

dp는 2차원 배열로, dp[i][j]는 i번째 집을 j 색깔로 칠했을 때의 최소 비용을 나타냄!

2. DP 계산

i번째 집을 칠할 때, 인접한 집의 색상을 고려하여 최소 비용을 계산

• i번째 집을 빨간색으로 칠할 때, i-1번째 집은 초록색 또는 파란색으로 칠해야 함
• dp[i][Red]는 dp[i-1][Green]과 dp[i-1][Blue] 중 작은 값에 현재 집의 빨간색 비용을 더한 값
  👉 현재 Red 비용값 + Math.min( 이전 누적 Green 비용값 ,이전 누적 Blue 비용값 )

  dp[i][Red] = Math.min(dp[i - 1][Green], dp[i - 1][Blue]) + r;

이와 같은 방식으로 초록색과 파란색 비용도 계산!

3. 최소 비용 출력

마지막 집(N번째 집)을 빨간색, 초록색, 파란색으로 칠했을 때의 최소 비용 중 가장 작은 값을 출력!

Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2]))

2번째 풀이

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

public class Main {

    static int N;
    static final int RED = 0;
    static final int GREEN = 1;
    static final int BLUE = 2;

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

        N = Integer.parseInt(br.readLine()); // 집
        int[] R = new int[N + 1];
        int[] G = new int[N + 1];
        int[] B = new int[N + 1];

        for(int i = 1; i <= N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            R[i] = Integer.parseInt(st.nextToken());
            G[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
        }

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

        // 1번 집 초기화
        dp[1][RED] = R[1];
        dp[1][GREEN] = G[1];
        dp[1][BLUE] = B[1];

        for (int i = 2; i <= N; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == RED) {
                    dp[i][j] = Math.min(dp[i - 1][GREEN], dp[i - 1][BLUE]) + R[i];
                }
                if (j == GREEN) {
                    dp[i][j] = Math.min(dp[i - 1][RED], dp[i - 1][BLUE]) + G[i];
                }
                if (j == BLUE) {
                    dp[i][j] = Math.min(dp[i - 1][RED], dp[i - 1][GREEN]) + B[i];
                }
            }
        }

        /**
        for (int i = 2; i <= N; i++) {
            // 지금 탐색하는 집이 해당 색으로 칠해질때의 최소 비용 계산
            dp[i][RED] = Math.min(dp[i - 1][GREEN], dp[i - 1][BLUE]) + R[i];
            dp[i][GREEN] = Math.min(dp[i - 1][RED], dp[i - 1][BLUE]) + G[i];
            dp[i][BLUE] = Math.min(dp[i - 1][RED], dp[i - 1][GREEN]) + B[i];
        }
        */

        int ans = Math.min(dp[N][BLUE], Math.min(dp[N][RED], dp[N][GREEN]));

        System.out.print(ans);

    }
}

만약 여기서

R, G, B .... 배열의 종류가 많아진다면 cost 2차원 배열을 두고 계산하는 것이 낫곘다!

int[][] cost = new int[N + 1][3]; // cost 

        for(int i = 1; i <= N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            cost[i][RED] = Integer.parseInt(st.nextToken());
            cost[i][GREEN] = Integer.parseInt(st.nextToken());
            cost[i][BLUE] = Integer.parseInt(st.nextToken());
        }