[Java] 백준 1149번 - RGB거리

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

 

 

 

 

접근 방식

 

 

가장 먼저 생각나는 것은 그리디적인 접근이었다. i번째 집을 고를 때, i-1에서 선택된 색깔을 제외하고 가장 저렴한 집을 고르는 방식이었는데, 설계를 한 후 대입해봤을 때 다음과 같은 테스트케이스에서 최솟값을 구하지 못할 것으로 예상되었다.

	R	G	B
i - 1번째 집	32	83	55
i번째 집	51	37	63
i + 1번째 집	89	29	100

 

 

 

 

 

 

즉 완전 탐색을 해야하는 케이스인데, 내가 선택한 것은 재귀호출 + 백트래킹이었다.

 

/**
*  cnt번째 집의 cost를 구하는 재귀함수 (cnt : 0 -> N)
*/
public static void getMinCost(int[][] cost, int cnt, int cur, int prev) {
	if (cnt == cost.length) {
		min = Math.min(min, cur);
		return;
	}
		
	// 백트래킹
	if (cur >= min) {
		return;
	}
	
	for (int c = 0; c < 3; c++) {
        if (c == prev) {
			continue;
		}
		getMinCost(cost, cnt + 1, cur + cost[cnt][c], c);
	}
}

 

 

하지만 이와 같이 재귀호출을 할 경우, N의 크기가 커질 수록 시간 또한 기하급수적으로 늘어났기 때문에 N의 최댓값이 1000인 이 문제에서는 시간 초과가 발생했다. 따라서 시간을 줄이기 위해서 이전 연산 결과를 기록해둘 필요가 있었다. 

 

 

 

 

 

따라서 동적계획법(DP)을 이용하여 이전까지의 누적 연산 결과를 기록하는 방식으로 전체적인 리팩토링을 했다.

 

/**
	*  cnt번째 집의 누적 cost를 구하는 재귀함수 (cnt : 1 -> N)
	*/
	public static void getCost(int[][] dp, int[][] cost, int cnt) {
		if (cnt > N) {
			min = Math.min(Math.min(dp[N][0], dp[N][1]), dp[N][2]);
			return;
		}
		
		dp[cnt][0] = Math.min(dp[cnt-1][1], dp[cnt-1][2]) + cost[cnt][0];
		dp[cnt][1] = Math.min(dp[cnt-1][0], dp[cnt-1][2]) + cost[cnt][1];
		dp[cnt][2] = Math.min(dp[cnt-1][0], dp[cnt-1][1]) + cost[cnt][2];
		
		getCost(dp, cost, cnt + 1);
	}

 

 

 

 

 

 

전체 코드

 

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

public class Main {
	
	static int N;
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int[][] cost = new int[N+1][3];
		int[][] dp = new int[N+1][3];
		
		// 색상 입력받음
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		getCost(dp, cost, 1);
		System.out.println(min);
		
	}
	
	/**
	*  cnt번째 집의 누적 cost를 구하는 재귀함수 (cnt : 1 -> N)
	*/
	public static void getCost(int[][] dp, int[][] cost, int cnt) {
		if (cnt > N) {
			min = Math.min(Math.min(dp[N][0], dp[N][1]), dp[N][2]);
			return;
		}
		
		dp[cnt][0] = Math.min(dp[cnt-1][1], dp[cnt-1][2]) + cost[cnt][0];
		dp[cnt][1] = Math.min(dp[cnt-1][0], dp[cnt-1][2]) + cost[cnt][1];
		dp[cnt][2] = Math.min(dp[cnt-1][0], dp[cnt-1][1]) + cost[cnt][2];
		
		getCost(dp, cost, cnt + 1);
	}
}