[백준] 4883 삼각 그래프 - 동적계획법(DP, Dynamic Programming) JAVA

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

4883번: 삼각 그래프

코드설명

동적계획법(DP, Dynamic Programming) 을 활용하는 문제입니다.

 

문제에서 map[][] 은 각각 현재줄에서의 첫번째, 두번째, 세번째 수를 선택했을때의 최소 비용을 나타냅니다.

 

문제에서 유의해야할점들입니다.

1. 그림의 화살표 방향을 이해해야합니다.

즉, 반드시 내려가는것이 아닌, 옆을 거치면서도 갈 수 있습니다.

 

2. 시작점은 반드시 map[0][1] 입니다.

시작점은 반드시 map[0][1]이므로 사실상 map[0][0] 을 거칠일은 없습니다. 또한 그래프 그림을 보면 실제로 map[0][1]에서 map[0][0]으로 가는 길이 없습니다. 

 

3. 끝점은 반드시 map[N-1][1] 입니다. (끝점도 가운데로 고정되어있습니다.)

 

저는 가장 첫번쨰 행과 두번째 행은 시작점이 고정되어있어 먼저 처리한 후에 아래부터는 반복문을 사용해 일반화시켜 게산했습니다.

코드

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

public class Main {
	public static int N, M, K;
	public static int answer = 0;
	public static int[][] map;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int T = 0;
    	while(true) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		K = Integer.parseInt(st.nextToken());
    		if(K == 0)
    			return ;
    		
    		map = new int[K][3];
    		dp = new int[K][3];
    		for(int i=0;i<K;i++) {
    			st = new StringTokenizer(br.readLine());
    			int a = Integer.parseInt(st.nextToken());
    			int b = Integer.parseInt(st.nextToken());
    			int c = Integer.parseInt(st.nextToken());
    			
    			map[i][0] = a;
    			map[i][1] = b;
    			map[i][2] = c;
    			
    		}
    		simulate();
    		T+=1;
    		System.out.println(T+". "+map[K-1][1]);
    	}
    }
    
    public static void simulate() {
    	
    	map[0][2] += map[0][1];
    	
    	map[1][0] += map[0][1];
    	map[1][1] += Math.min(map[1][0], Math.min(map[0][1], map[0][2]));
    	map[1][2] += Math.min(map[0][1], Math.min(map[1][1], map[0][2]));
    	
    	for(int i=2; i<K;i++) {
    		map[i][0] = Math.min(map[i-1][0], map[i-1][1]) + map[i][0];
    		map[i][1] = Math.min(Math.min(map[i][0], map[i-1][0]), Math.min(map[i-1][1], map[i-1][2])) + map[i][1];
    		map[i][2] = Math.min(Math.min(map[i][1], map[i-1][1]), map[i-1][2]) + map[i][2];
    	}
    	
    }
}

 

정답코드2입니다.

재귀와 메모이제이션을 활용합니다.

아래의 코드를 작성하면서 놓쳤었던 부분은, 

//  ret = Math.min(ret, DFS(depth - 1, next) ) + matrix[depth][now];
    ret = Math.min(ret, DFS(depth - 1, next) + matrix[depth][now]);

이 코드입니다.

저는 처음에 주석처리한 코드방식으로 작성했습니다만, 오류가 났습니다.

왜 그럴까요?

바로,  여러번 matrix[depth][now]가 더해질 수 있다는 점입니다.

예시를 들어보겠습니다.

만약 첫번쨰 재귀에서 DFS(depth -1, next)로 갱신되고, matrix[depth][now]까지 더해졌습니다.

두번째 재귀에서 이전 ret이 min값이고 이번의 재귀값은 min값이 아니었습니다. 하지만 여전히 matrix[depth][now]가 더해집니다.

이렇게 되면 계속 ret값에 추가값이 더해지겠지요.

그러므로 DFS(depth -1, next) + matrix[depth][now] 와 같이 두번쟤 방식으로 코드를 작성해야만 중복 더하기 연산이 발생하지 않습니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int[] answer = new int[2];
	static int[][] matrix;
	static long[][] cache = new long[100001][3];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int num = 0;
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			if(N == 0) return ;
			matrix = new int[N][3];
			for(int i=0; i<100001; i++) {
				Arrays.fill(cache[i], -1);
			}
			for(int i=N-1;i>=0; i--) {
				st = new StringTokenizer(br.readLine());
				for(int j=0; j<3; j++) {
					matrix[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			System.out.println(++num+". "+ DFS(N-1, 1));
			
		}
	}
	
	static long DFS(int depth, int now) {
		if(depth == 0 && now == 1) return matrix[depth][now];
		if(depth == -1) return 100000 * 1000 + 1; 
		if(cache[depth][now] != -1) return cache[depth][now];
		long ret = 100000 * 1000 + 1;
		if(now == 0) {
			ret = Math.min(ret, DFS(depth, 1) + matrix[depth][now]);
		}
		if(now == 1) {
			ret = Math.min(ret, DFS(depth, 2) + matrix[depth][now]);
		}
		for(int dir : new int[] {-1, 0, 1}) {
			int next = now + dir;
			if(next < 0 || next >= 3) continue;
//			ret = Math.min(ret, DFS(depth - 1, next) ) + matrix[depth][now];
			ret = Math.min(ret, DFS(depth - 1, next) + matrix[depth][now]);
		} 
		return cache[depth][now] = ret;
	}
	
}