[백준] 1149번 : RGB거리(JAVA)

멀고도 험난한 Dynamic Programming Master의 길...

https://www.acmicpc.net/problem/1149

1149번: RGB거리

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 14단계

 

동적 계획법 1의 카테고리에 포함되어 있는 문제이다.

 

혼자 해결해보려고 했다가 힘들어서 검색을 통해 이해하고 문제를 해결하였다.

 

문제를 스스로 해결하지 못해 안타깝지만 시간이 지나면 더 나아져있을 것이라고 믿고 더 노력해야겠다.

 

문제의 예시에서 첫 번째 집을 칠하는 비용은 26 40 83이다.

 

그 다음 첫 번째 집을 칠하고 두 번째 집을 칠할 때 최소비용은 49+40 60+26 57+26 이다.

 

마지막으로 세 번째 집을 칠할 때 최소비용은 89+89 86+13 83+13 이다.

 

마지막 집을 칠하고 나서의 배열에 저장된 최솟값이 문제의 정답이다.

 

import java.util.Scanner;

public class Question_1149 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[][] House = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			House[i][0] = sc.nextInt();
			House[i][1] = sc.nextInt();
			House[i][2] = sc.nextInt();
		}
		
		for(int i = 1; i < N; i++) {
			House[i][0] += Math.min(House[i-1][1], House[i-1][2]);
			House[i][1] += Math.min(House[i-1][0], House[i-1][2]);
			House[i][2] += Math.min(House[i-1][0], House[i-1][1]);
		}
		System.out.println(Math.min(House[N-1][0], Math.min(House[N-1][1], House[N-1][2])));
	}

}