초콜릿과 건포도 [SWEA 9282][Java]

 

[광고 누르면 오늘의 행운 상승!!]

 

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

문제의 저작권은 SW Expert Academy에 있습니다.

완탐을 하면 시간초과가 난다.

메모리 제이션 기법을 활용하여 각 구역의 건포도 값을 저장한 배열을 만들어서

값이 구해져 있다면 계산하지 않게 하였다.

import java.io.*;
import java.util.*;

public class Solution {
	static int result;
	static int N,M;
	static int[][] map;
	static int[][][][] dp;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			map = new int[N][M];
			dp  = new int[N+1][M+1][N+1][M+1];
			
			for(int[][][] d1 : dp) {
				for(int[][] d2 : d1) {
					for(int[] d3 : d2) {
						Arrays.fill(d3, Integer.MAX_VALUE);
					}
				}
			}
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			result = dfs(0,0,N,M);
			
			System.out.println("#" + tc + " " + result);
		}
	}
	public static int dfs(int y, int x, int h, int w) {
		if(w == 1 && h == 1) {
			return 0;
		}
		//기존에 있던 덩어리의 건포도 개수
		int sum = 0;
		for (int i = y; i < y + h; i++) {
			for (int j = x; j < x + w; j++) {
				sum += map[i][j];
			}
		}
		//가로로 나누어서 비용을 최소비용을 구한다.
		for (int i = 1; i < h; i++) {
			//위쪽 비용
			if(dp[y][x][i][w] == Integer.MAX_VALUE) {
				dp[y][x][i][w] = dfs(y,x,i,w);
			}
			//아래쪽 비용
			if(dp[y+ i][x][h- i][w] == Integer.MAX_VALUE) {
				dp[y+ i][x][h- i][w] = dfs(y + i , x, h - i , w);
			}
			//건포도의 개수
			int sum3 = sum + dp[y][x][i][w] + dp[y+ i][x][h- i][w];
			dp[y][x][h][w] = Math.min(dp[y][x][h][w], sum3);
		}
		//세로로 나누어서 비용을 최소비용을 구한다.
		for (int i = 1; i < w; i++) {
			//왼쪽 비용
			if(dp[y][x][h][i] == Integer.MAX_VALUE) {
				dp[y][x][h][i] = dfs(y,x,h,i);
			}
			//오른쪽 비용
			if(dp[y][x + i][h][w - i] == Integer.MAX_VALUE) {
				dp[y][x + i][h][w - i] = dfs(y, x + i, h, w - i);
			}
			//건포도의 개수
			int sum3 = sum + dp[y][x][h][i] + dp[y][x + i][h][w - i];
			dp[y][x][h][w] = Math.min(dp[y][x][h][w], sum3);
		}
		return dp[y][x][h][w];
	}

}