백준 1149 RGB거리

기본적인 DP 문제이다.

 

임의의 한 지점(i 번째)에 있는 집이 빨강일 때, 초록일 때 파랑일 때로 나누어서 생각한다.

1)빨강일 때: min(i-1번 째 있는 집이 파랑, i-1번 째 있는 집이 노랑) + i번째가 빨강일 때 칠하는 비용

2)초록일 때: min(i-1번 째 있는 집이 빨강, i-1번 째 있는 집이 파랑) + i번째가 초록일 때 칠하는 비용

3)파랑일 때: min(i-1번 째 있는 집이 빨강, i-1번 째 있는 집이 초록) + i번째가 파랑일 때 칠하는 비용

 

따라서 DP 배열을 선언할 때 2차원 배열로 선언하고 dp[n][3]으로 생선한다.(n은 집의 개수, 3은 빨강,초록,파랑)

마지막 최솟값은 n번째 집의 min(빨강,초록,파랑) 이다.

 

코드는 아래와 같다.

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

public class Main1149 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st;
		int n = Integer.parseInt(br.readLine());

		// 0: 빨강, 1: 초록, 2: 파랑
		int[][] input = new int[n][3];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			input[i][0] = Integer.parseInt(st.nextToken());
			input[i][1] = Integer.parseInt(st.nextToken());
			input[i][2] = Integer.parseInt(st.nextToken());
		}

		int[][] dp = new int[n][3];
		dp[0][0] = input[0][0];
		dp[0][1] = input[0][1];
		dp[0][2] = input[0][2];

		for (int i = 1; i < n; i++) {
			dp[i][0] = (dp[i - 1][1] + input[i][0] < dp[i - 1][2] + input[i][0]) ? dp[i - 1][1] + input[i][0]
					: dp[i - 1][2] + input[i][0];
			dp[i][1] = (dp[i - 1][0] + input[i][1] < dp[i - 1][2] + input[i][1]) ? dp[i - 1][0] + input[i][1]
					: dp[i - 1][2] + input[i][1];
			dp[i][2] = (dp[i - 1][0] + input[i][2] < dp[i - 1][1] + input[i][2]) ? dp[i - 1][0] + input[i][2]
					: dp[i - 1][1] + input[i][2];
		}
		int ans = min(dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]);
		System.out.println(ans);
	}

	private static int min(int i, int j, int k) {
		int ret;
		if (i < j)
			ret = i;
		else
			ret = j;

		if (ret > k)
			ret = k;
		return ret;
	}

}