[백준] 1149 RGB거리 - 동적계획법(DP, Dynamic Programming) JAVA

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

1149번: RGB거리

코드설명

DP문제입니다.

 

DP[N][3] : DP[N][] 는 N번째 집에 페인트를 칠할때 가능한 최소 비용입니다.

 

DP[i][j] = i번째 집을 더할떄 j번째 페인트를 칠할때의 최소 비용입니다. 이떄 만약

DP[2][1] 이라면 2번째 집에 초록색 페인트를 칠할경우의 최소비용을 구하는 것입니다. 이떄 첫번쨰 집의 빨간색을 칠할떄 최소비용 혹은 첫번쨰 집의 파란색을 칠할떄의 최소비용중 둘중에 가능한 비용을 구해서 비교하여 최소값을 넣어주면 됩니다.

if( j == 0) {
    dp[i][j] = Math.min(dp[i-1][j+1], dp[i-1][j+2]) + arr[i][j];	
}
else if( j == 1) {
    dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j+1]) + arr[i][j];	
}    			
else if( j == 2) {
    dp[i][j] = Math.min(dp[i-1][j-2], dp[i-1][j-1]) + arr[i][j];	
}

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N, M;
	public static int[][] arr;
	public static int[][] dp;
	public static int answer = 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());
    	arr = new int[N][3];
    	dp = new int[N][3];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<3;j++) {
    			arr[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	dp[0][0] = arr[0][0];
    	dp[0][1] = arr[0][1];
    	dp[0][2] = arr[0][2];
    	
    	for(int i=1;i<N;i++) {
    		
    		for(int j=0;j<3;j++) {
    			if( j == 0) {
    				dp[i][j] = Math.min(dp[i-1][j+1], dp[i-1][j+2]) + arr[i][j];	
    			}
    			else if( j == 1) {
    				dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j+1]) + arr[i][j];	
    			}    			
    			else if( j == 2) {
    				dp[i][j] = Math.min(dp[i-1][j-2], dp[i-1][j-1]) + arr[i][j];	
    			}    			
    		}
    	}

    	
    	
    	
    	answer = Math.min(dp[N-1][0], dp[N-1][1]);
    	answer = Math.min(answer, dp[N-1][2]);
    	
    	System.out.println(answer);
    }
}

 

메모이제이션 + 재귀를 활용한 코드입니다.

유의사항은  + arr[depth][homeIdx] 로 현재 위치의 값을 함수가 끝날떄 더해준다는 점입니다.

만약 다음 값을 처리한다면 불필요하게 첫번쨰 값을 따로 처리해야하므로 현재 배열값을 처리해주는것이 더 효율적인것 같습니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, L, R;
	static int answer = 0;
	static int[][] arr = new int[1001][3];
	static int[][] cache = new int[1001][3];
	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());
		for(int i=0;i<N; i++) {
			Arrays.fill(cache[i], -1);
			
			st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			arr[i][2] = Integer.parseInt(st.nextToken());
		}
		
		answer = dfs(-1, -1);
		
		System.out.println(answer);
	}
	
	static int dfs(int depth, int homeIdx) {
		if(depth == N) return 0;
		int ret = 1000 * 1000 + 1;
		if(depth == -1 && homeIdx == -1) {
			ret = Math.min(ret, dfs(depth + 1, 0));
			ret = Math.min(ret, dfs(depth + 1, 1));
			ret = Math.min(ret, dfs(depth + 1, 2));
			return ret;
		}
		
		if(cache[depth][homeIdx] != -1) return cache[depth][homeIdx];
		
		if(homeIdx == 0) {
			ret = Math.min(ret, dfs(depth+1, 1) + arr[depth][0]);
			ret = Math.min(ret, dfs(depth+1, 2) + arr[depth][0]);
		}
		else if(homeIdx == 1) {
			ret = Math.min(ret, dfs(depth+1, 0) + arr[depth][1]);
			ret = Math.min(ret, dfs(depth+1, 2) + arr[depth][1]);
		}else if(homeIdx == 2) {
			ret = Math.min(ret, dfs(depth+1, 0) + arr[depth][2]);
			ret = Math.min(ret, dfs(depth+1, 1) + arr[depth][2]);
		}
		
		return cache[depth][homeIdx] = ret;
	}
}