1149번:RGB거리[Java]

문제

처음에 줄 수를 입력을 한 후 각 줄마다 R, G, B 숫자를 입력한다.

최소비용을 구하는데 인접한 집끼리는 색이 겹치면 안된다.

예를 들어 3번 집에 초록색을 칠한다면, 2번집과 4번 집은 초록색을 칠 할 수 없다. 

이번 문제는 재귀를 이용하여 풀어보았다. 

import java.util.*;

public class Main {
	
	final static int r = 0;
	final static int g = 1;
	final static int b = 2;
	static int[][] house;
	static int[][] min;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	int n=0;
	
	n=sc.nextInt(); //줄수 입력받기
	
	house = new int [n][3];  // n은 줄수 // 2차원 배열은 각 집의 비용
	min = new int[n][3];
	
	for(int i=0;i<n;i++){ //각 집들의 비용 입력받기 

			house[i][r]=sc.nextInt();
			house[i][g]=sc.nextInt();
			house[i][b]=sc.nextInt();
		
	}
	
	
	
	// min의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
			min[0][r] = house[0][r];
			min[0][g] = house[0][g];
			min[0][b] = house[0][b];
			
			
			
	System.out.print(Math.min(sort(n- 1, r), Math.min(sort(n - 1, g), sort(n - 1, b))));
	}
static int sort(int n, int color) {
		
		// 만약 탐색하지 않은 배열이라면
		if(min[n][color] == 0) {
			
			// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 min에 저장한다
			if(color == r) {
				min[n][r] = Math.min(sort(n - 1, g), sort(n - 1, b)) + house[n][r];
			}
			else if(color == g) {
				min[n][g] = Math.min(sort(n - 1, r), sort(n - 1, b)) + house[n][g];
			}
			else {
				min[n][b] = Math.min(sort(n - 1, r), sort(n - 1, g)) + house[n][b];
			}
			
		}
		
		return min[n][color];
	}


}

 

실행결과

정답이다.

 

Math.min을 이용하여 최솟값을 구해주면 제한시간안에 구할 수 있다.