[백준,BOJ 1149] RGB 거리(JAVA 구현)

-내 생각

  동적 프로그래밍을 풀기 전까지 백 트래킹 문제들을 풀어서 그런지 이 문제를 보자마자 백 트래킹 방식으로 풀 생각을 해버렸다.. 도저히 어떻게 풀어야 될지 모르겠어서 다른 분들의 글을 참고했다.

 

-해법

  우선 이 문제 역시 점화식을 세워주어야 한다. https://m.blog.naver.com/occidere/220785383050

[백준] 1149 - RGB거리 (2017-12-02 수정완료)

  이 분의 블로그에 잘 정리가 되어 있기 때문에 자세한 설명은 생략하겠다.

 

import java.util.*;

public class Main {
	static int n;
	
	static int dp[][], cost[][]; // DP 배열과 비용 배열을 선언
	
	
	public static void main(String[] args)   {
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		
		dp = new int[1001][3];
		cost = new int[1001][3];
		
		for(int i=1;i<=n;i++) {
			for(int j=0;j<3;j++) {
				cost[i][j] = sc.nextInt();
			}
		}
		
		
		for(int i=1;i<=n;i++) {
        
        	// 점화식을 세워준다.
			dp[i][0] = Math.min(dp[i-1][1],dp[i-1][2]) + cost[i][0];
			dp[i][1] = Math.min(dp[i-1][0],dp[i-1][2]) + cost[i][1];
			dp[i][2] = Math.min(dp[i-1][1],dp[i-1][0]) + cost[i][2];
		}
		
		System.out.println(Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2])));
		
			
		
		
		
		
		
		
		
		
	}
	
}