[Java/백준/DP] 1149번: RGB거리

문제

www.acmicpc.net/problem/1149

1149번: RGB거리

 

코드

나한테 미지의 세계인 문제였다.... DP는 문제 맞닥뜨릴 때마다 이게 뭔데 하게 됨 ㅠ

 

코드는 아래 링크를 참고했다.

m.blog.naver.com/occidere/220785383050

[백준] 1149 - RGB거리 (2017-12-02 수정완료)

 

int a[1001][3] : 각 집에 대한 채색 비용이 들어간다

int d[1001][3] : i번째 집을 j색으로 칠했을 때의 비용

 

그럼 처음에 점화식을 이렇게 세울 수 있다.

d[i] = d[i-1] + 최솟값(a[i])

 

하지만 d[i-1] 번째 값을 최솟값으로 칠했다 해도 다음 집도 최솟값이 되는 보장이 없다.

 

따라서 최종 적으로 이런 점화식을 세울 수 있다.

d[i][0] = min(d[i-1][1], d[i-1][2]) + a[i][0]

d[i][1] = min(d[i-1][0], d[i-1][2]) + a[i][1]

d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][2]

 

이 때 i==1이라면, 0번째 집도 언급된다.

하지만 0번째는 칠할 집도 없으므로 0원으로 설정해주면 된다.

d[0][0] = d[0][1] = d[0][2] = a[0][0] = a[0][1] = a[0][2] = 0

(물론 초기화하면서 0으로 값이 설정되긴 함ㅎ)

 

이렇게 하면 마지막에 d[n][0], d[n][1], d[n][2] 셋 중 최솟값을 구하면 된다.

 

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

class Main{
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[][] homes = new int[N+1][3];
        int[][] homes_cost = new int[N+1][3];
        
        for(int i=1; i<=N; i++){
            String[] str = br.readLine().split("\\s");
        	homes[i][0] = Integer.parseInt(str[0]);
        	homes[i][1] = Integer.parseInt(str[1]);
        	homes[i][2] = Integer.parseInt(str[2]);
        }
        
        for(int i=1; i<=N; i++){
        	homes_cost[i][0] = Math.min(homes_cost[i-1][1],homes_cost[i-1][2])+homes[i][0];
        	homes_cost[i][1] = Math.min(homes_cost[i-1][0],homes_cost[i-1][2])+homes[i][1];
        	homes_cost[i][2] = Math.min(homes_cost[i-1][0],homes_cost[i-1][1])+homes[i][2];
        }
        
        int result = Math.min(Math.min(homes_cost[N][0], homes_cost[N][1]),homes_cost[N][2]);
        
        bw.write(result+"\n");
        bw.flush();
    }
}