백준 1149번 : RGB 거리 자바

 

 

🧫 문제 분석

 

✔️ 출처

RGB 거리 실버 1

 

📖 문제

 

DP 문제로

현재 집 비용 + 이전 집에서 현재 집 열이 아닌 2 곳 중 가장 적은 비용을 가진다.

 

점화식을 세워보면 이렇다. 

dp[i][j] = Math.min(dp[i][j+1], dp[i][j+2]) + house[i][j];

물론 한 행에 집은 3개이므로 현재 열을 제외한 다른 집 중에서 가장 적은 비용을 선택하므로

% 연산이나 if문을 써서 현재 집 열을 피하면 된다. 

 

 

---

🔅 문제 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        int[][] graph = 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++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dp[0][0] = graph[0][0];
        dp[0][1] = graph[0][1];
        dp[0][2] = graph[0][2];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < 3; k++) {
                    if (j != k){
                        dp[i][j] = Math.min(dp[i - 1][k] + graph[i][j], dp[i][j]);
                    }
                }
            }
        }

        int min = Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]);
        bw.write(min + "");
        bw.flush();
        bw.close();
    }
}

 

나머지 연산을 할 경우

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Math.min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + graph[i][j];
            }
        }

더 깔끔하다.

 

❗ 오답노트 / 필요한 지식

1.  간단한 DP 문제였다.