사용한 것
- 연속된 색상을 선택하지 않고 집을 색칠하는 최소 비용을 구하기 위한 bottom-up
풀이 방법
- 연속 색상은 선택할 수 없다.
- 따라서 R, G, B 색상 별로 각각 자신의 색상을 제외한 가격들 중 최소를 구하여 넣어준다.
- 마지막 집이 R, G, B로 색칠된 결과 중 가장 최소 가격을 출력한다.
코드
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[][] dArr = new int[N + 1][3];
for (int i = 1; i <= N; i++) {
int[] arr = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
dArr[i] = arr;
}
int[][] d = new int[N + 1][3];
d[1][0] = dArr[1][0];
d[1][1] = dArr[1][1];
d[1][2] = dArr[1][2];
for (int i = 2; i <= N; i++) {
d[i][0] = Math.min(d[i - 1][1], d[i - 1][2]) + dArr[i][0];
d[i][1] = Math.min(d[i - 1][0], d[i - 1][2]) + dArr[i][1];
d[i][2] = Math.min(d[i - 1][0], d[i - 1][1]) + dArr[i][2];
}
int min = d[N][0];
for (int i = 1; i < 3; i++) {
if (d[N][i] < min) {
min = d[N][i];
}
}
System.out.println(min);
}
}