백준 1149 RGB거리 JAVA (DP)

1. 문제

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

1149번: RGB거리

 

2. 설명

N을 기준으로

N-1이 R일 경우, G일 경우, B일 경우를 모두 고려해서 최솟값을 구해야한다. (두 번째 for문)

그렇게 dp배열에 저장하고, 그 중 최솟값이 비용의 최솟값이 된다.

1번집부터 시작하기 때문에 배열의 크기는 N+1로 잡았다.

 

3. 코드

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 집의 수
		int[][] cost = new int[N+1][3]; // 1번 집부터 시작
		int[][] dp = new int[N+1][3];
		
		for(int i=1; i<=N; i++) {
			st = new StringTokenizer(br.readLine());
			cost[i][0] = Integer.parseInt(st.nextToken());
			cost[i][1] = Integer.parseInt(st.nextToken());
			cost[i][2] = Integer.parseInt(st.nextToken());
		}
		
		dp[1][0] = cost[1][0];
		dp[1][1] = cost[1][1];
		dp[1][2] = cost[1][2];
		
		for(int i=2; 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][0], dp[i-1][1]) + cost[i][2];
		}
		
		int answer = dp[N][0];
		for(int i=0; i<3; i++) {
			if(answer > dp[N][i]) answer = dp[N][i];
		}
		System.out.println(answer);
	}
}