130. 1149(RGB 거리)

import java.util.*;
import java.io.*;

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[][] num = new int[N][3];

		for (int i = 0; i < N; i++) {
			String[] tmp = br.readLine().split(" ");
			num[i][0] = Integer.parseInt(tmp[0]);
			num[i][1] = Integer.parseInt(tmp[1]);
			num[i][2] = Integer.parseInt(tmp[2]);
		}

		for (int i = 1; i < N; i++) {
			num[i][0] += Math.min(num[i - 1][1], num[i - 1][2]);
			num[i][1] += Math.min(num[i - 1][0], num[i - 1][2]);
			num[i][2] += Math.min(num[i - 1][0], num[i - 1][1]);
		}

		System.out.println(Math.min(Math.min(num[N-1][0], num[N-1][1]), num[N-1][2]));
	}

}

문제요약

각 집을 세가지 색 중에서 가장 저렴한 색으로 칠하여 모든 집을 칠하는데 최소비용을 구하라. (단, N번째 기준 N-1과 N+1집의 색은 같으면 안된다.)

설명

단순히 인덱스가 다르고 그 중에서 최소값을 구하면 되겠구나라고 생각할 수 있다.

그렇다면,

다음과 같을 때 답일 것이다.

 

하지만 

다음과 같이 더 적은 값으로 모든 집을 칠할 수 있다.

따라서 각 케이스 마다 인덱스가 다르고, 최소 값이 아닌 현재 케이스에서 최소값이 아니더라도 다음 케이스에서 작은 값을 더함으로 써 더 낮은 비용이 나올 수 있도록 해야한다.

 

따라서 누적합을 통해 이를 해결할 수 있다.

num[i][0] += Math.min(num[i - 1][1], num[i - 1][2]);
num[i][1] += Math.min(num[i - 1][0], num[i - 1][2]);
num[i][2] += Math.min(num[i - 1][0], num[i - 1][1]);

현재 케이스의 인덱스와 겹치지 않고 전 케이스의 인덱스에서 작은 값을 더하면서 누적 합을 구해나간다.

Math.min(Math.min(num[N-1][0], num[N-1][1]), num[N-1][2])

세가지의 누적합을 구하게 되는데 그 중 가장 작은 값을 고르면 된다.