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

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

SW Expert Academy

---

문제 해석

이 문제는 N x M 크기의 초콜릿을 1x1 크기로 완전히 나누려고 할 때, 최소한의 건포도 수를 포함하여 나누는 전략을 찾는 것이다. 건포도의 수는 각 조각에 미리 할당되어 있으며, 나눌 때마다 해당 영역의 건포도 합이 비용으로 추가된다.

풀이 과정

• 동적 프로그래밍(DP) 접근: 이 문제는 4차원 DP 배열 dp[x][y][h][w]을 사용하여 (x, y) 위치에서 시작하고 (h, w) 크기를 가진 영역을 나누는 데 필요한 최소 비용을 저장한다.
• 재귀와 메모이제이션: dfs 함수를 통해 재귀적으로 최소 분할 비용을 계산하며, 이미 계산된 영역은 메모이제이션을 통해 중복 계산을 방지한다.
• 영역 분할: 각 영역을 수직 혹은 수평으로 분할하여 그 비용을 계산하고, 각 분할에 대한 최소값을 찾는다.

코드

package edu.ssafy.im.SWEA.D4.No9282;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
    private static int TC, N, M;   // 테스트 케이스 수, 행과 열의 크기
    private static int[][] map;    // 초콜릿 각 칸에 대한 건포도 수 저장
    private static int[][][][] dp; // DP 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        TC = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력
        for (int T = 1; T <= TC; T++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            map = new int[N][M]; // 초콜릿 지도 초기화
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < M; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            dp = new int[N+1][M+1][N+1][M+1]; // DP 배열 초기화
            for (int[][][] d1 : dp) {
                for (int[][] d2 : d1) {
                    for (int[] d3 : d2) {
                        Arrays.fill(d3, Integer.MAX_VALUE); // 최대값으로 초기화
                    }
                }
            }

            sb.append("#").append(T).append(" ").append(dfs(0, 0, N, M)).append("\n"); // 결과 추가
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int dfs(int x, int y, int h, int w) {
        if (h == 1 && w == 1) return 0; // 1x1이면 나눌 필요 없음

        int sum = 0; // 현재 영역의 건포도 수 합
        for (int i = x; i < x + h; i++) {
            for (int j = y; j < y + w; j++) {
                sum += map[i][j];
            }
        }

        for (int i = 1; i < h; i++) { // 수직으로 나누기
            if (dp[x][y][i][w] == Integer.MAX_VALUE) dp[x][y][i][w] = dfs(x, y, i, w);
            if (dp[x + i][y][h - i][w] == Integer.MAX_VALUE) dp[x + i][y][h - i][w] = dfs(x + i, y, h - i, w);
            dp[x][y][h][w] = Math.min(dp[x][y][h][w], sum + dp[x][y][i][w] + dp[x + i][y][h - i][w]);
        }

        for (int i = 1; i < w; i++) { // 수평으로 나누기
            if (dp[x][y][h][i] == Integer.MAX_VALUE) dp[x][y][h][i] = dfs(x, y, h, i);
            if (dp[x][y + i][h][w - i] == Integer.MAX_VALUE) dp[x][y + i][h][w - i] = dfs(x, y + i, h, w - i);
            dp[x][y][h][w] = Math.min(dp[x][y][h][w], sum + dp[x][y][h][i] + dp[x][y + i][h][w - i]);
        }

        return dp[x][y][h][w]; // 최소 비용 반환
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N^3 * M^3)로 계산될 수 있다. 모든 가능한 영역에 대하여 분할을 시도하기 때문에, 최악의 경우 모든 분할 가능성을 계산해야 한다.

느낀점

이 문제를 통해 다차원 DP와 메모이제이션의 중요성을 다시 한번 느꼈다. 초기에 최적화를 고려하지 않고 접근했을 때는 시간 초과가 발생했었는데, 메모이제이션을 적절히 사용하면서 문제를 해결할 수 있었다. 이러한 복잡한 문제를 통해 문제 해결 능력과 알고리즘 이해도가 향상되었다고 느낀다.