백준 1149번 : RGB거리 (Java)

🔗 문제 링크

 

1149번: RGB거리

---

📖 풀이 과정

 

- 다이나믹 프로그래밍 유형 + 재귀 유형의 문제입니다.
- 문제의 조건을 종합해보면, 현재 인덱스의 최소값은 바로 직전 색깔을 제외한 다른 두가지 색깔중에서 최소값을 더한 값입니다.
- 그렇기에 어떠한 한 색깔의 특정 인덱스에서의 값은 이전 색깔을 제외한 두가지 색깔중에 최소값을 구해야 합니다.
- 이러한 방식으로 답을 찾아나가면, 답이 될 수 있는 값은 빨강색, 초록색, 파란색 3가지입니다. 
- 따라서, 이 세가지 값에 대한 dp 배열의 최솟값을 출력하면 답입니다.
- 아마, 글로 작성해서는 이해가 되지 않을 수 있습니다. 그렇다면, solve 메소드의 로직을 하나씩 따라가보시면 흐름을 이해하실 수 있을 겁니다.

 

---

💻 코드

 

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

public class Main {
 static int n,answer;
 static int[][] arr;
 static int[][] dp;
 
 public static void main(String[] args) throws IOException {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  n = Integer.parseInt(br.readLine());
  arr = new int[n][3];
  dp = new int[n][3];
  answer = 0;
  
  for(int i = 0; i< n; i++){
   StringTokenizer st = new StringTokenizer(br.readLine()," ");
   for(int j = 0; j< 3; j++){
    arr[i][j] = Integer.parseInt(st.nextToken());
   }
  }
  dp[0][0] = arr[0][0];
  dp[0][1] = arr[0][1];
  dp[0][2] = arr[0][2];
 
  int answer = Math.min(solve(n-1,0),Math.min(solve(n-1,1),solve(n-1,2)));
  System.out.println(answer);
 }
 
 private static int solve(int idx, int color){
  if(dp[idx][color] == 0){
   if(color == 0){
    dp[idx][0] = Math.min(solve(idx-1,1),solve(idx-1,2)) + arr[idx][0];
   }else if(color == 1){
    dp[idx][1] = Math.min(solve(idx-1,0),solve(idx-1,2)) + arr[idx][1];
   }else if(color == 2){
    dp[idx][2] = Math.min(solve(idx-1,0),solve(idx-1,1)) + arr[idx][2];
   }
  }
  return dp[idx][color];
 }
}