https://www.acmicpc.net/problem/1149
정답률 55.322%
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
3
26 40 83
49 60 57
13 89 99
96
이웃한 집의 색은 겹치면 안된다. 결국 N번째 집까지 색칠했을 때 최소 비용을 구해야 하므로 N번째 집의 색깔마다 최소 비용의 누적합을 구한다. 각 누적합은 N-1번째로부터 구할 수 있다. 즉 동적 계획법으로 풀이한다.
각 색깔마다의 누적합을 구하는 점화식은 다음과 같다.
N-1번째의 다른 색깔의 누적합 중 더 작은 값을 기존 비용에 누적한다.
//백준
public class Main {
private static final int RED = 0;
private static final int GREEN = 1;
private static final int BLUE = 2;
static int[][] house;
static int[][] dp;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
house = new int[N][3];
dp = new int[N][3];
//입력값 초기화
for (int i = 0; i < N; i++) {
house[i] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
//dp 초기화
dp[0] = house[0];
System.out.println(Math.min(calCost(RED, N - 1),
Math.min(calCost(GREEN, N - 1), calCost(BLUE, N - 1))));
}
//최소비용 계산 메서드
static int calCost(int color, int N) {
//탐색하지 않은 원소일 경우
if (dp[N][color] == 0) {
dp[N][color] = house[N][color];
if (color == RED) {
dp[N][RED] += Math.min(calCost(GREEN, N - 1), calCost(BLUE, N - 1));
}
else if (color == GREEN) {
dp[N][GREEN] += Math.min(calCost(RED, N - 1), calCost(BLUE, N - 1));
}
else if (color == BLUE) {
dp[N][BLUE] += Math.min(calCost(RED, N - 1), calCost(GREEN, N - 1));
}
}
//N번째 누적합 반환
return dp[N][color];
}
}