링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW9j-qfacIEDFAUY

해설

부르트포스 + 2차원배열구간합 + 4차원 배열 메모리제이션 사용

⇒ 알고리즘 적인 난이도가 높은 문제인거 같음

1. 부르트 포스

   현재 초콜릿 좌표 (xs,ys) ,(xf,yf) 사이에 가로 또는 새로로 초콜릿을 자르는 모든 경우를 해봐야함

2. 2차원 배열 구간합

   초콜릿을 자르게 되면 해당 구간의 총합 만큼의 점수를 얻는데 해당 점수를 구하기위 해 2차원 배열 구간합을 이용

3. 메모리 제이션

   check[xs][ys][xf][yf] ⇒ (xs,ys) 에서 (xf,yf) 구간의 초콜릿을 자를때 얻는 점수를 부르트포수 도중 다시 방문하지 않게 저장해 두어야함

코드

import java.util.Scanner;
import java.io.FileInputStream;
 
 
class Solution
{
    static int[][][][] check;
    static int DQ(int xs, int xf, int ys, int yf, int[][] board, int[][] prefixSum) {
        int boardSum = prefixSum[xf + 1][yf + 1] - prefixSum[xf+1][ys] - prefixSum[xs][yf + 1] + prefixSum[xs][ys];
//        System.out.println(prefixSum[xf][yf] + " " + boardSum);
        int wresult = 987654321;
        int hresult = 987654321;
				//이미 이전에 점수를 구했었다면 더 진행하지않고 메모리제이션된 값을 리턴
        if (check[xs][ys][xf][yf]!=-1) return check[xs][ys][xf][yf];
        if (xs > xf || ys > yf) return 0;
        if (xs == xf && ys == yf) return 0;
				//높이 구간에서 자른경우
        for (int mid = xs; mid < xf; mid++) {
            hresult = Math.min(hresult, DQ(xs, mid, ys, yf, board, prefixSum) + DQ(mid + 1, xf, ys, yf, board, prefixSum));
        }
				 //넒이 구간에서 자른경우
        for (int mid = ys; mid < yf; mid++) {
            wresult = Math.min(wresult, DQ(xs, xf, ys, mid, board, prefixSum) + DQ(xs, xf, mid + 1, yf, board, prefixSum));
        }
				//메모리 제이션 배열 갱신
        check[xs][ys][xf][yf] = boardSum + Math.min(hresult, wresult);
        return boardSum + Math.min(hresult, wresult);
 
 
    }
 
    public static void main(String args[])  {
 
        Scanner sc = new Scanner(System.in);
        int T;
        T = sc.nextInt();
 
 
        for (int test_case = 1; test_case <= T; test_case++) {
            int h = sc.nextInt();
            int w = sc.nextInt();
            int[][] board = new int[h][w];
						//메모리 제이션 배열 초기화
            check = new int[h][w][h][w];
            for(int i = 0; i < h; i++){
                for(int j=0;j<w;j++){
                    for(int k=0;k<h;k++){
                        for(int z=0;z<w;z++){
                            check[i][j][k][z]=-1;
                        }
                    }
                }
            }
            int[][] prefixSum = new int[h + 1][w + 1];
 
 
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    board[i][j] = sc.nextInt();
 
                }
            }
 
 
            for (int i = 1; i < h+1; i++) {
                for (int j = 1; j < w+1; j++) {
                    prefixSum[i][j] = board[i - 1][j - 1] - prefixSum[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1];
                }
            }
//            for(int[] arr : prefixSum){
//                System.out.println(Arrays.toString(arr));
//            }
 
            //System.out.println(tmp);
            System.out.println("#" + test_case + " " + DQ(0, h - 1, 0, w - 1, board, prefixSum));
        }
    }
}