[BOJ] 백준 [1149] RGB거리 JAVA

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

1149번: RGB거리

문제

풀이

첫 번째 집을 무슨 색으로 칠 하느냐에 따라서 결과가 달라지고 이전 집과는 다른 색을 칠해야 하므로

그리디로는 접근이 불가능하다.

 

만약 i 번째 집을 R로 색칠 하고 싶다고 가정을 하자. 

그럼 i-1 번째 집은 R이 아니어야 한다.

 

=> i-1 번째집을 [G 로 색칠 했을때 총비용] 과 [B 로 색칠 했을때 총 비용] 중 작은 것을 선택 해야한다.

이런 식으로 하면 R로 칠할때 , G로 칠할때, B로 칠할때 총 3가지의 다른 경우가 나온다.

색칠 할 수 있는 경우의 수는 3가지 이므로 2차원배열의 dp[집 개수][색 종류] 로 정의 할 수 있다.

 

더 도식화 해보면 i 번째 집을 k 로 칠하고 싶다고 가정을 하면 , k는 3가지(RGB) 색이므로

다음과 같이 점화식을 도출 할 수 있다.

 

for(int k=0;k<3;k++)
dp[i][k] = Math.min(dp[i-1][(k+1)%3] , dp[i-1][(k+2)%3])+arr[i][k];

 

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));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][3]; // 0:R 1:G 2:B
        for(int i=0;i<n;i++)
            arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
 
        int[][] dp = new int[n][3];
        dp[0][0] = arr[0][0]; dp[0][1] = arr[0][1]; dp[0][2] = arr[0][2];
 
        for(int i=1;i<n;i++){
            for(int k=0;k<3;k++)
                dp[i][k] = Math.min(dp[i-1][(k+1)%3] , dp[i-1][(k+2)%3])+arr[i][k];
        }
        System.out.println(Math.min(Math.min(dp[n-1][0],dp[n-1][1]),dp[n-1][2]));
    }
}

ez..