백준 1149번 RGB거리 [JAVA]

 

DP(Dynamic programming) 알고리즘 문제이다.

2차원 배열을 선언하고 다음행을 입력할 때, 

이전의 행 중 최소값을 더해서 입력한다.

그렇게 R,G,B 총 3개의 경우를 고려하고

 

가장 마지막 행의 값 중 가장 작은 값을 출력하면 정답이다.

package codingTest_backjoon;

import java.util.Scanner;

//RGB거리
public class Main_1149 {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		
		int row = scan.nextInt();
		
		int[][] arg = new int[row][3];
		
		for(int i=0; i<row; i++) {
			
			int R = scan.nextInt();
			int G = scan.nextInt();
			int B = scan.nextInt();
			
			if(i == 0) {
				arg[i][0] = R;
				arg[i][1] = G;
				arg[i][2] = B;
			}else {
				arg[i][0] = R + Math.min(arg[i-1][1], arg[i-1][2]);
				arg[i][1] = G + Math.min(arg[i-1][0], arg[i-1][2]);
				arg[i][2] = B + Math.min(arg[i-1][0], arg[i-1][1]);
			}
			
		}
		
		int min = arg[row-1][0];
		for(int i=0; i<arg[0].length; i++) {
			if(min > arg[row-1][i]) {
				min = arg[row-1][i];
			}
		}
		System.out.println(min);
	}
}