백준 동적계획법 - 1149번 : RGB 거리

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

1149번: RGB거리

---

import java.io.*;
import java.util.*;


public class Main {
		public static int[][] memo;
		public static int[][] house;
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		house = new int[n][3];
		memo = new int[n][3];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			house[i][0] = Integer.parseInt(st.nextToken());
			house[i][1] = Integer.parseInt(st.nextToken());
			house[i][2] = Integer.parseInt(st.nextToken());
		}
		for(int i=0; i<3;i++) {
			memo[0][i] = house[0][i];
		}
		for(int i=1; i<n; i++) {
			memo[i][0] = house[i][0]+ Math.min(memo[i-1][1], memo[i-1][2]);
			memo[i][1] = house[i][1]+Math.min(memo[i-1][0], memo[i-1][2]);
			memo[i][2] = house[i][2]+Math.min(memo[i-1][1], memo[i-1][0]);
		}
		int min = Integer.MAX_VALUE;
		for(int i=0; i<3;i++) {
			if(memo[n-1][i]<min) {
				min = memo[n-1][i];
			}
		} 
		bw.write(min+"");
		bw.close();
	}
}

n번째 줄에서 봤을 때 색이 겹치지 않는 n-1번째 비용 두 개 중 작은 값을 더해서 누적시키는 방식으로 풀었다.