알고리즘 풀이/백준

[백준][Java] 1149번 RGB거리

배게 2018. 5. 1. 02:45
728x90

DP의 기본이 되는 문제입니다.


상식적으로 첫째 줄부터 최소값으로 시작한다고 한다고

마지막 비용이 최소값이 아니라는 것만 숙지하여

점화식을 정의하는 법을 배우고

모든 줄의 각각의 RGB까지 도달할 때의 최소값을 구합니다.


문제에서 요구하는 마지막줄까지의 최소 비용은

마지막줄의 R, G, B까지 도달할때 의 최소비용 3개중 가장 작은 값을

출력시키면 됩니다.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Main {
	
	
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		int [][]min = new int[T+1][3];
		int[][] a= new int[T+1][3];
		
		
		for(int i=1; i<=T; i++) {
			for (int j=0; j<3;j++) {
				a[i][j]=sc.nextInt();
			}
		}
		
		min[0][0]=min[0][1]=min[0][2]=a[0][0]=a[0][1]=a[0][2]=0;
		
		for(int i=1; i<=T; i++) {
			min[i][0]=Min(min[i-1][1],min[i-1][2])+a[i][0];
			min[i][1]=Min(min[i-1][0],min[i-1][2])+a[i][1];
			min[i][2]=Min(min[i-1][0],min[i-1][1])+a[i][2];
		}
		
		System.out.println(Min(Min(min[T][0],min[T][1]),min[T][2]));
	}
	
	public static int Min(int a,int b) {return a<b? a:b;}
	
}