[백준 1149] RGB거리 (Java)

 

	빨간색	초록색	파란색
집 1	26	40	83
집 2	49	60	57
집 3	13	89	99
집 4	14	52	32
집 5	85	23	65

 

정수삼각형 문제랑 비슷하다.

첫번째 집부터 n번째 집까지 차근차근 더해주면 되는데 마지막 비용만 비교하면 된다.

또, i번째 집을 색칠할 땐 i-1번째 집이랑 다른 색으로만 칠하면 된다. (i+1번째 집 신경쓸 필요 없음)

i-1번째 비용까지 구했다면 차근차근 비용이 누적된거임 (1,2,3,...,i-1까지)

 

1) i번째 집을 빨간색으로 칠할 경우

i-1번째 집을 파란색으로 칠한 비용 + i-번째집 빨간색으로 칠할때 비용 vs i-1번째 집을 초록색으로 칠한 비용 + i-번째집 빨간색으로 칠할때 비용

 

2) i번째 집을 초록색으로 칠할 경우

i-1번째 집을 빨간색으로 칠한 비용 + i-번째집 초록색으로 칠할때 비용 vs i-1번째 집을 파란색으로 칠한 비용 + i-번째집 초록색으로 칠할때 비용

 

3) i번째 집을 파란색으로 칠할 경우

i-1번째 집을 빨간색으로 칠한 비용 + i-번째집 파란색으로 칠할때 비용 vs i-1번째 집을 초록색으로 칠한 비용 + i-번째집 파란색으로 칠할때 비용

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n+1][n+1];
 
        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=1; j<=3; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
 
        for(int i=2; i<=n; i++){
            arr[i][1]=Math.min(arr[i][1]+arr[i-1][2], arr[i][1]+arr[i-1][3]);
            arr[i][2]=Math.min(arr[i][2]+arr[i-1][1], arr[i][2]+arr[i-1][3]);
            arr[i][3]=Math.min(arr[i][3]+arr[i-1][1], arr[i][3]+arr[i-1][2]);
        }
 
        int ans=0;
        ans = arr[n][1]<arr[n][2]?arr[n][1]:arr[n][2];
        ans = ans<arr[n][3]?ans:arr[n][3];
        System.out.println(ans);
    }
}