import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Q1149 {
public static void main(String[] args) throws IOException {
int[][] houses = input();
output(houses);
}
static int[][] input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] houses = new int[n][3];
for (int i = 0; i < n; i++) {
String[] inputStrings = br.readLine().split(" ");
for (int j = 0; j < 3; j++) {
houses[i][j] = Integer.parseInt(inputStrings[j]);
}
}
return houses;
}
static void output(int[][] houses){
int n = houses.length;
int[][] dp = new int[n][3];
for (int i = 0; i < 3; i++) {
dp[0][i] = houses[0][i];
}
for (int i = 1; i < n; i++) {
dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = houses[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = houses[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
}
}
이 규칙들을 지켜서 집들을 칠한다고 가정할 때 위와 같이 집들의 색칠이 이루어질 것이다.
static int[][] input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] houses = new int[n][3];
for (int i = 0; i < n; i++) {
String[] inputStrings = br.readLine().split(" ");
for (int j = 0; j < 3; j++) {
houses[i][j] = Integer.parseInt(inputStrings[j]);
}
}
return houses;
}
먼저 각 집마다 색칠할 때의 입력값들을 받아준다.
houses라는 2차원 정수 배열을 생성한다. 이 배열은 각 집마다 색칠하는 비용을 저장하는 배열이다. 집의 개수는 n이 될 것이고, n개의 집마다 3개의 색으로 집을 색칠할 것이기 때문에 [n][3]의 크기의 정수형 배열을 초기화하여 준다.
그리고 입력한 값들을 정수로 변환하여 배열에 저장한다.
static void output(int[][] houses){
int n = houses.length;
int[][] dp = new int[n][3];
for (int i = 0; i < 3; i++) {
dp[0][i] = houses[0][i];
}
for (int i = 1; i < n; i++) {
dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = houses[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = houses[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
}
}
문제에서 요구하는 것은 모든 집을 색칠하는 비용의 최솟값을 구하는 것이다.
나의 풀이 방식은 집을 색칠할 때 최솟값을 저장하는 2차원 배열 dp를 초기화하여주는 것이다.
for (int i = 0; i < 3; i++) {
dp[0][i] = houses[0][i];
}
첫 번째 집은 기존의 색칠 비용이 존재하지 않기 때문에 houses의 첫번째 값과 동일하다.
이를 제외한 dp의 각 배열값들은 다음과 같이 구성될 것이다.
dp의 n번째 값은 n-1까지의 최소비용과 해당 집의 각 색칠에 따른 비용을 저장하게 된다.
또한 해당 규칙을 준수하여야 하므로
for (int i = 1; i < n; i++) {
dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
dp[i][1] = houses[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
dp[i][2] = houses[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
}
다음과 같이 코드를 작성하였다.
그림에서는 n-1까지의 최소비용이라고 동일하게 작성하였지만, 0번 색깔 즉 해당 집을 빨간색으로 칠할 경우 그 전의 집의 색깔은 그 색깔로 칠하지 않아야 하므로
dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
다음과 같이 최소 비용이 저장되어야 한다.
이처럼 n번 순회하면서 dp의 값을 채워주면 각 색칠에 따른 집들의 최소 색칠비용들로 dp의 값들이 저장되게 된다.
System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
이후 각 색칠에 따른 최소색칠 비용들을 비교하여 얻은 최솟값이 모든 집을 칠하는 비용의 최솟값이 된다.