[백준온라인] 17404번 RGB거리 2

문제 : https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

문제 요약 : 모든 집을 칠하는 비용의 최솟값을 출력한다.

입력	출력
2 ≤ N(집의 수) ≤ 1000 1 ≤ c(비용) ≤ 1000	모든 집을 칠하는 최소 비용 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_17404.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
31139157	cbkpar	17404	맞았습니다!!	14548KB	152ms	Java 11	1522B

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

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n,i,t,m;
		n = Integer.parseInt(br.readLine());
		int[][] dp = new int[n][9];
		dp[0][0] = dp[0][1] = 1000000000;
		dp[0][3] = dp[0][5] = 1000000000;
		dp[0][7] = dp[0][8] = 1000000000;
		StringTokenizer st = new StringTokenizer(br.readLine());
		dp[0][6] = Integer.parseInt(st.nextToken());
		dp[0][4] = Integer.parseInt(st.nextToken());
		dp[0][2] = Integer.parseInt(st.nextToken());
		for(i=1;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			t = Integer.parseInt(st.nextToken());
			dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + t;
			dp[i][3] = Math.min(dp[i-1][4], dp[i-1][5]) + t;
			dp[i][6] = Math.min(dp[i-1][7], dp[i-1][8]) + t;
			t = Integer.parseInt(st.nextToken());
			dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + t;
			dp[i][4] = Math.min(dp[i-1][3], dp[i-1][5]) + t;
			dp[i][7] = Math.min(dp[i-1][6], dp[i-1][8]) + t;
			t = Integer.parseInt(st.nextToken());
			dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + t;
			dp[i][5] = Math.min(dp[i-1][3], dp[i-1][4]) + t;
			dp[i][8] = Math.min(dp[i-1][6], dp[i-1][7]) + t;
		}
		dp[n-1][2] = 1000000000;
		dp[n-1][4] = 1000000000;
		dp[n-1][6] = 1000000000;
		m = Integer.MAX_VALUE;
		for(i=0;i<9;i++) m = Math.min(m, dp[n-1][i]);
		System.out.println(m);
	}
}

배열을 [n][9] 크기로 만들어 

[n][0~2]는 첫 번째 집을 빨강으로 색칠로 했을 경우

[n][3~5]는 첫 번째 집을 초록으로 색칠로 했을 경우

[n][6~8]는 첫 번째 집을 파랑으로 색칠로 했을 경우

 

[i][0,3,6]은 i번째 집을 빨강으로 칠한 비용

[i][1,4,7]은 i번째 집을 초록으로 칠한 비용

[i][2,5,8]은 i번째 집을 파랑으로 칠한 비용

 

이때 해당 i번째 집을 색칠하는 비용은

i번째 집을 해당 색으로 색칠하는 최소비용은

그 이전의 해당색을 제외한 집을 색칠한 최소비용과 i번째 집을 해당 색으로 색칠하는 값의 합이다.

 

예를 들어 i번째 집을 빨강으로 칠하는 경우는

i번째 집을 빨강으로 칠하는 비용 + i-1번째 집을 파랑 혹은 초록으로 칠하는 비용 중 작은 값이다.

 

마지막으로

빨강으로 시작했을 경우 빨강으로 끝나는 경우 또는

초록으로 시작했을 경우 초록으로 끝나는 경우 또는

파랑으로 시작했을 경우 파랑으로 끝나는 경우

위 3가지 경우를 제외해야 하므로 해당 값을 비용의 최대값으로 수정 후

해당 마지막배열의 최솟값을 출력한다.