[Algorithm] RGB 거리 색칠하기

이번 문제는 RGB색깔을 이용하여 차례대로 색칠을 하되 이웃한 색이 겹치지 않는 선에서

값의 최솟값을 구하는 문제 였다. 문제의 최솟값을 구하는 문제는 거의다 DP 혹은

greed알고리즘으로 해결 할 수 있는데 위 문제는 greed문제로 해결 할 수 없을 꺼 같아

DP로 생각을 해보았다.

먼저 이 문제를 해결 하기 위해 처음에 간단하게 C[n](n번째 집을 색칠 할 때의 최솟값)을

구하려 했는데 생각해보니 조금 다르게 생각을 해야 됬다.

이 문제를 해결 하기 위해선 N번째 집의 최솟 값은 N번째 집을 각각 R G B 의 cost로

칠 했을 때의 값 들 중 최솟값을 구하면 되는 문제다. 이렇게 문제를 생각하니 그 다음부턴

수월하게 해결 할 수 있었다.

[ 그림 참고 - http://devdasom.tistory.com/24]

위와 같이 각각의 색깔 (R G B)의 색 에 대해 배열을 설정 하고 N번 째 집의 색깔을 정할 땐

그 이전 값 중 현재 색을 제외 한 값의 Maximum값을 더하면 되는 문제다. 수식으로 보자.

위와 같은 방법으로 각각 R , G , B 색 에 대한 값을 N까지 구한 후 마지막 RGB값들 중 

최소값을 구하면 해결 !!

소스코드:

package algorithm;

import java.util.Scanner;

public class a_1149 {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int N = sc.nextInt();

int[][] cost = new int[3][N];

final int R = 0;

final int G = 1;

final int B = 2;

cost[R][0] = sc.nextInt();

cost[G][0] = sc.nextInt();

cost[B][0] = sc.nextInt();

for (int i = 1; i < N; i++) {

int r = sc.nextInt();

int g = sc.nextInt();

int b = sc.nextInt();

cost[R][i] = r + Math.min(cost[G][i - 1], cost[B][i - 1]);

cost[G][i] = g + Math.min(cost[R][i - 1], cost[B][i - 1]);

cost[B][i] = b + Math.min(cost[R][i - 1], cost[G][i - 1]);

}

System.out.println(Math.min(cost[B][N - 1], Math.min(cost[R][N - 1], cost[G][N - 1])));

}

}