[백준] 1149 RGB거리(Java)

백준 - 1149 RGB거리

풀이

DP로 해결

1. 입력받은 값을 rgb 2차원 배열에 저장
2. rgb와 같은 사이즈의 2차원 배열 dp 선언
3. dp에 최소 비용으로 칠하는 경우의 금액을 저장
4. 1번째 집이 R로 칠했다면 -> 2번째 집은 R로 칠해야 함
5. 각자 집을 칠하는데 i 번째 집과 i + 1 번째 집의 색이 다르고, i 번째 집과 i - 1 번째 집의 색깔도 달라야 하는 조건
   ❗️이웃한 집과 색을 다르게 칠해야 하고, 이웃한 집들은 같은 색일 수 있음

rgb 배열: 각 집을 RGB로 칠하는 비용
   R  G  B
   0  1  2
0 [26 40 83]
1 [49 60 57]
2 [13 89 99]


dp 배열: 각 집을 R,G,B로 칠하는 비용의 최소값을 저장
   R  G  B
   0  1  2
0 [26 40 83]
1 [89 86 83]
2 [96 172 185]

• dp[1][0] = 1번째 집이 R인 경우 -> 0번째 집은 R로 칠할 수 없음, G나 B로 칠해야 함 = <0번째 G,B 중 최솟값 + 1번째 R값> = 40 + 49 = 89
• dp[1][1] = 1번째 집이 G인 경우 -> 0번째 집은 G로 칠할 수 없음, R이나 B로 칠해야 함 = <0번쨰 R,B 중 최솟값 + 1번째 G값> = 26 + 60 = 86
• dp[1][1] = 1번째 집이 B인 경우 -> 0번째 집은 B로 칠할 수 없음, R이나 G로 칠해야 함 = <0번쨰 R,G 중 최솟값 + 1번째 B값> = 26 + 57 = 83

dp[i][j] = i번째 집이 j인 경우 -> i-1번째 집은 j로 칠할 수 없음, j가 아닌 값으로 칠해야 함

✔️j 값은 0, 1, 2
(j == 0) 인 경우, dp[i][j] = min(dp[i-1][1], dp[i-1][2]) + rgb[i][j]
(j == 1) 인 경우, dp[i][j] = min(dp[i-1][0], dp[i-1][2]) + rgb[i][j]
(j == 2) 인 경우, dp[i][j] = min(dp[i-1][0], dp[i-1][1]) + rgb[i][j]

마지막 집까지 다 칠한 후, 마지막 집의 RGB 중 최소값이 정답

j의 값이 0, 1, 2인 것을 지정해놓고 풀어서 아쉽긴 하지만, 일단 제출..

코드

import java.util.Arrays;
import java.util.Scanner;

public class RGBstreet {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int size = Integer.parseInt(scanner.nextLine());
		int[][] rgb = new int[size][3];
		int[][] dp = new int[size][3];
		for (int i = 0; i < size; i++) {
			String[] tmp = scanner.nextLine().split(" ");
			for (int j = 0; j < 3; j++) {
				rgb[i][j] = Integer.parseInt(tmp[j]);
			}
		}
		dp[0] = rgb[0];
		for (int i = 1; i < size; i++) {
			for (int j = 0; j < 3; j++) {
				int tmp;
				if (j == 0) tmp = Math.min(dp[i - 1][1], dp[i - 1][2]);
				else if (j == 1) tmp = Math.min(dp[i - 1][0], dp[i - 1][2]);
				else tmp = Math.min(dp[i - 1][0], dp[i - 1][1]);
				dp[i][j] = tmp + rgb[i][j];
			}
		}

		System.out.println(Arrays.stream(dp[size - 1]).min().getAsInt());
	}
}