[SWEA] 초콜릿과 건포도

[9282] 초콜릿과 건포도

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

• 가로 M, 세로 N 크기의 초콜릿이 있다.
• i행 j열 격자에는 A(ij)개의 건포도가 들어있으며,
• 자르기 전 초콜릿에 들어 있는 전체 건포도 t개가 들어있을 경우
• 이를 자르는 행위의 비용을 t라고 한다.
• 초콜릿을 자르는 행위를 반복하여 N*M개의 조각으로 자르려고 할 때 최소비용을 구하는 문제

 

 

Solution

• 건포도의 누적합을 미리 구한 뒤 가로자르기, 세로자르기 방법으로 자른 비용의 최솟값을 dp 배열에 저장하는 방법
• 자르는 행위에 대한 비용이 어떤 조각으로 자르냐에 따라 달라지기 때문에 최소 비용을 dp 배열에 저장한다.
• dp[x][y][ex][ey] = 왼쪽 상단(x, y) 오른쪽 하단(ex, ey) 크기의 초콜릿을 더이상 자를 수 없을 때 까지 잘랐을 때 드는 최소 비용

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
    static int T, n, m;
    static int[][] arr, sumArr;
    static int[][][][] dp;
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = stoi(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            st = new StringTokenizer(br.readLine());
            n = stoi(st.nextToken());
            m = stoi(st.nextToken());
 
            init();
 
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < m; j++) {
                    arr[i][j] = stoi(st.nextToken());
                    sumArr[i + 1][j + 1] = sumArr[i + 1][j] + sumArr[i][j + 1] + arr[i][j] - sumArr[i][j];
                }
            }
 
            System.out.println("#" + tc + " " + solve(1, 1, n, m));
        }
    }
 
    static int solve(int x, int y, int ex, int ey) {
        if (x == ex && y == ey)
            return 0;
        int ret = dp[x][y][ex][ey];
        if (ret > 0)
            return ret;
        ret = Integer.MAX_VALUE;
 
        int value = sumArr[ex][ey] - sumArr[ex][y - 1] - sumArr[x - 1][ey] + sumArr[x - 1][y - 1];
 
        // 가로 자르기
        for (int i = x; i < ex; i++) {
            ret = Math.min(ret, value + solve(x, y, i, ey) + solve(i + 1, y, ex, ey));
        }
 
        // 세로 자르기
        for (int i = y; i < ey; i++) {
            ret = Math.min(ret, value + solve(x, y, ex, i) + solve(x, i + 1, ex, ey));
        }
 
        return dp[x][y][ex][ey] = ret;
    }
 
    static void init() {
        arr = new int[n][m];
        sumArr = new int[n + 1][m + 1];
        dp = new int[n + 1][m + 1][n + 1][m + 1];
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}