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

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

SW Expert Academy

이 문제는 구간 누적 합을 메모해 놓을 배열과 최솟값을 메모해 놓을 배열이 각각 필요하다.

 

다음과 같은 로직으로 풀어봤다.

 

1. 입력받는다.
2. 누적합을 dp로 만들어 놓는다.
   dp[x][y] = (0, 0)이 왼쪽 시작점 (x, y)과 오른쪽 끝점인 사각형의 누적합
3. 초콜릿 자르는 모든 경우를 분할정복으로 구해준다.
   1. 가로로 자르는 경우(for문으로 가로 선택하는 모든 경우 구한다)
   2. 세로로 자르는 경우(for문으로 세로 선택하는 모든 경우 구한다)

위의 3번의 모든 경우 중 건포도의 수가 최소인 경우를 구해준다.
하지만 이때 진짜 다 구하면 시간 초과 발생하므로 미리 구해놓은 거는 메모해놨다가 써야 한다.

 

dp[x][y][ex][ey] = 초콜릿의 왼쪽 시작점이 (x, y) 오른쪽 끝점이 (ex, ey) 일 때 초콜릿을 자르는 경우 지불해야 하는 건포도의 최솟값

 

초콜릿의 크기가 클수록 다시 사용되는 부분이 계속 존재하므로 매번 다시 구할 필요가 없다. 그림으로 설명하면

아래 그림처럼 어떻게 잘라도 노란 사각형 부분을 잘랐을 때의 건포도의 최솟값은 동일하기 때문이다.

 

 

누적합을 구하는 방법은 백준의 2167번 2차원 배열의 합(문제 링크)을 푸는 방법과 똑같다.

(풀이 링크)

#include <iostream>
#include <cstring>
#define MAX 1000000000
using namespace std;
 
int dp[51][51][51][51];
int choco[51][51];
int sum[51][51];
 
int solve(int x, int y, int ex, int ey) {
    //초코릿 조각이 한개면 0리턴
    if (x == ex && y == ey) return 0;
    //이미 최솟값을 구해놨으면 최솟값 바로 리턴
    if (dp[x][y][ex][ey] != -1) {
        return dp[x][y][ex][ey];
    }
 
    //(x, y)부터 (ex, ey)까지의 건포도의 합
    int cnt = sum[ex][ey] - sum[x - 1][ey] - sum[ex][y - 1] + sum[x - 1][y - 1];
 
 
    int rt = MAX;
 
    //가로로 자르는 경우
    for (int i = x; i < ex; i++) {
        int tmp = solve(x, y, i, ey) + solve(i + 1, y, ex, ey);
        if (rt > tmp + cnt) rt = tmp + cnt;
    }
 
    //세로로 자르는 경우
    for (int i = y; i < ey; i++) {
        int tmp = solve(x, y, ex, i) + solve(x, i + 1, ex, ey);
        if (rt > tmp + cnt) rt = tmp + cnt;
    }
 
 
    //dp메모하고 리턴
    return dp[x][y][ex][ey] = rt;
 
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
 
    int T;
    cin >> T;
 
    int n, m;
    for (int tc = 1; tc <= T; tc++) {
        //최솟값 dp배열 -1로 초기화
        memset(dp, -1, sizeof(dp));
        
        cin >> n >> m;
 
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> choco[i][j];
            }
        }
 
        //누적합
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + choco[i][j];
            }
        }
 
        int ans = solve(1, 1, n, m);
        cout << '#' << tc << ' ' << ans << '\n';
    }
 
 
    return 0;
}