[백준] 17404 - RGB거리 2

 

[문제링크]

17404번: RGB거리 2

 

0. 1번집의 색 != N번집의 색이어야 한다

 

1. 1번집을 단색으로 제한한 후 RGB값을 각각 구한다

  - 1번집을 R로 설정 -> N번집이 G/B로 끝나는 최솟값 구하기

  - 1번집을 G로 설정 -> N번집이 R/B로 끝나는 최솟값 구하기

  - 1번집을 B로 설정 -> N번집이 R/G로 끝나는 최솟값 구하기

 

2. 전체 결과 6가지 중 최솟값이 정답

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = pint(br.readLine());
		cost = new int[N][3];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			cost[i][0]=pint(st.nextToken());
			cost[i][1]=pint(st.nextToken());
			cost[i][2]=pint(st.nextToken());
		}
		
		min=Integer.MAX_VALUE;
		
		temp=new int[N][3];
		temp[0][0]=cost[0][0];temp[0][1]=2000000;temp[0][2]=2000000;
		run(0);
		
		temp=new int[N][3];
		temp[0][0]=2000000;temp[0][1]=cost[0][1];temp[0][2]=2000000;
		run(1);

		temp=new int[N][3];
		temp[0][0]=2000000;temp[0][1]=2000000;temp[0][2]=cost[0][2];
		run(2);
		
		System.out.println(min);
	}
	static int[][] temp;
	static int[][] cost;
	static int min,N;
	static void run(int notPick) {
		for (int i = 1; i < N; i++) {
			temp[i][0]=Math.min(temp[i-1][1], temp[i-1][2])+cost[i][0];
			temp[i][1]=Math.min(temp[i-1][0], temp[i-1][2])+cost[i][1];
			temp[i][2]=Math.min(temp[i-1][1], temp[i-1][0])+cost[i][2];
		}
		for (int i = 0; i < 3; i++) {
			if(i!=notPick && temp[N-1][i]<min)min=temp[N-1][i];
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면