[백준][자바] 1149 - RGB거리 - DP

📌 문제

백준 | RGB거리 | SILVER 1 | DP

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

 

 

📌 문제 탐색하기

• RGB 거리에는 집이 N개 존재
  • 거리는 ‘선분’
  • 1~N번 집 존재
  • 빨, 초, 파 중 하나의 색
  ⇒ 각 비용이 존재할 때, 모든 집을 칠하는 비용의 MIN 값 구하기

 

• 규칙 :
  • 1번 집 색상 ≠ 2번 집 색상
  • N번 집 색상 ≠ N-1번 집 색상
  • i 번 집 색상 ≠ i-1 (2≤i≤n-1)
  • i 번 집 색상 ≠ i+1 (2≤i≤n-1)
• 입력 :
  • N (집의 수)
  • 집을 빨, 초, 파로 칠하는 비용 (1~N번 순서로)
• 출력 :
  • 모든 집을 칠하는 비용의 MIN 값

 

 

 

📌 알고리즘

• 이전의 계산 결과가 이 후의 계산에 영향을 주므로, DP를 활용해서 문제를 풀어야한다.
• DP를 풀땐, 규칙이 가장 중요한데…
  • 이 문제에서는 빨, 초, 파 3가지 경우가 존재하므로 3가지 모두 선정된다는 가정 하에 계산을 모두 진행하면서
  • 최종 행의 MIN값이 답이 될 것이다.

즉, 자기자신을 기준으로 나머지 2개에서 최소값을 더하면서 열3을 갱신해 나아가야한다.

 

📌 코드 설계하기

1. n, rgb, dp 초기화
2. rgb 배열 입력
3. dp 배열 입력 (rgb 자기자신 + 이전 행의 다른 열 중 최소값)

 

📌 시도 회차 수정 사항

1회차

• 배열의 크기를 처음에는 n으로 잡으니, 0일때 이전의 값을 불러 올 수 없어 문제가 발생했음 → n+1로 행의 크기를 넓히기

 

📌 정답 코드

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

public class Main {
    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[][] rgb = new int[n+1][3];
        int[][] dp = new int[n+1][3];

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

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

        int answer = Math.min(dp[n][0], dp[n][1]);
        answer = Math.min(answer, dp[n][2]);

        System.out.println(answer);
    }
}

 

DP 문제에서는 은근히 배열의 크기가 중요할 때가 많은 것 같다.

문제에 나온 예시를 근거로 차근차근 풀어보잣 🍀📢