백준 1149. RGB 거리

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

 

점화식을 세워 보기 위해 노력했는데, 나도 모르게 그리디 알고리즘(최적해를 계속 구하는 것이 아니라, 무조건 다음 값이 최적인 값만 찾아 이동하는 것)으로 풀었다. 제대로 된 풀이는 다음과 같다.

 

package test;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class test118 {
	static int N;
	static int[][] houses;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		N = Integer.parseInt(br.readLine());

		houses = new int[N][3];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				houses[i][j] = Integer.parseInt(st.nextToken());

			}
		}

		System.out.println(findBestColorCombination(N));

		bw.flush();
		bw.close();
		br.close();
	}

	static int findBestColorCombination(int N) {
		int[][] dp = new int[N][3];
		// 첫번째 값
		for (int i = 0; i < 3; i++) {
			dp[0][i] = houses[0][i];
		}

		for (int i = 1; i < N; i++) {
			dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + houses[i][0];
			dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + houses[i][1];
			dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + houses[i][2];
		}

		return Arrays.stream(dp[N - 1]).min().getAsInt();
	}
}