[ SWEA 9282 ] 초콜릿과 건포도 (C++)

SWExpertAcademy의 초콜릿과 건포도(9282 / D4) 문제이다.

[ 문제풀이 ]
먼저 문제에 대해서 이해하고 가보도록 하자.

초기 초콜릿이 위와 같은 형태로 존재한다고 가정해보자. 위의 맵 같은 경우 2 x 3 짜리 맵이기 때문에, 이 초콜릿을 2 x 3, 즉,
6개의 단일 블록이 나올 때 까지 잘라야 한다. 쉽게 이야기 해서 주어진 초콜릿을 모두 1x1 크기로 잘라야 한다는 것이다.
그럼 이 때, "초콜릿 한 조각을 두 조각으로 자를 때, 초기 큰 초콜릿에 있었던 건포도의 갯수만큼 지불" 에 대해 알아보자.
가장 초기 상태의 건포도의 갯수는 21개이다. 하나의 큰 초콜릿 조각이 있고, 그 안에는 총 21개의 건포도 수가 존재하는 것이다.
위의 초콜릿을 두 조각으로 잘라보자. 아마 몇 가지 경우만 적어보면 다음과 같이 나눌 수 있을 것이다.

뭐 이런 경우들이 존재할 것이다.
위와 같이, 크기를 두 조각으로 나눌 때, 즉, 초기상태에서 위의 상태로 변하게 되면 '21개'의 건포도를 주어야 한다는 것이다.

이런식으로 초콜릿이 1 x 1 크기의 N x M 개가 생겼을 때, 지불해야 할 최소 금액을 찾아야 하는 것이다.
본격적으로 초콜릿을 자르기에 앞서 지불해야 하는 건포도의 갯수를 구하는 법을 알아보자.
단순히 자를 때 마다, 구해도 되지만, 그렇게 할 경우 최악의 경우 2500번을 자를 동안 중복되는 부분을 계속해서 구해야 하기 때문에 시간초과가 발생할 수 있다.

여기서 중복되는 부분이라는 것은 간단하게 예를 들어보면 다음과 같은 상황이다.

위와같은 맵에서 저렇게 빨강색 선을 기준으로 잘랐다고 가정해보자. 그렇게 된다면, 그 다음턴에 우리가 구해야 할 건포도의 누적

합 부분은 다음과 같이 2부분이 있을 것이다.

파랑색 부분에 대한 누적 건포도의 합을 구해야 할 것이고, 초록색 부분의 누적 건포드의 합을 구해야 할 것이다.

그런데 반대로 다음과 같이 잘랐을 경우를 생각해보자.

이렇게 자르게 되면 구해야 할 부분이 다음과 같이 2가지 부분이 된다.

위에서 말한 가로로자르는 경우와, 세로로 자르는 경우 모두 다른 경우이기 때문에 따로따로 계산을 해서 최소값을 찾아내야

한다. 그렇다면, 매 경우마다 파랑색 사각형 초록색 사각형에 대한 누적합을 계속해서 구해야 한다는 것인데, 아래와 같이

노랑색으로 표시된 부분은 중복된 계산을 하게 된다.

만약, 자를 때 마다 누적합을 구하게 된다면 노랑색부분과 같이 중복된 부분에 대한 계산을 반복하게 된다.

물론, 위에서 말한 노랑색 부분은 발생할 수 있는 수 많은 경우 중 하나만 예를 들어서 설명한 것이다.

문제는 이런 경우가 엄청나게 발생할 수 있다는 것이다.

따라서, 자를 때 마다 맵 전체를 돌면서 누적합을 구하는 것 자체만으로도 시간의 부담이 있지만, 더 큰 부담은 중복된 부분을

계속해서 구한다는 것이다. 따라서 건포도의 갯수를 간단하게 계산할 수 있게 미리 세팅을 해주고 시작하자.

위의 맵에서 가장 왼쪽위의 좌표를 (1, 1) 가장 오른쪽 아래의 좌표를 (2, 3) 이라고 가정해보자.
그리고 지금부터 건포도의 누적 갯수는 Sum[][] 이라는 int형 2차원 배열에 저장한다고 이야기하겠다.
Sum[a][b] = c 의 의미는 (1, 1)에서 (a, b)까지의 건포도의 갯수는 총 c개 입니다 이다. 구체적인 의미는 아래에서 더 알아보자.
가장 먼저 Sum[1][1] = 1일 것이다. (1, 1)에서 (1, 1)까지의 건포드의 갯수는 1개이기 때문이다.
Sum[1][2]는 어떻게 될까 ? Sum[1][1] + MAP[1][2] 가 될 것이다. 즉, 1 + 2 = 3 개가 된다.
실제로 (1, 1)에서 (1, 2)까지 존재하는 건포도의 갯수는 1 + 2 개로 총 3개가 된다.
그럼 Sum[2][1]의 값을 구해보자. (1, 1)에서 (2, 1)까지의 갯수니까 (1, 1) + (1, 2) + (1, 3) + (2, 1) 일까 ??
아니면 위와 같이 자르는 경우를 대비해서 단순히 1 + 4 = 5 일까 ??
본인이 계산한 Sum[2][1]의 값은 5가 맞다. 그래서 위에서 Sum[a][b]의 의미를 설정할 때, 뒤에 "구체적인 의미는 ~" 이라는 말을
덧붙인 것이다. 위에서 말해놓은 정의만 본다면 (1, 1)에서 (a, b)까지의 건포도의 갯수니 (1, 1) + (1, 2) + (1, 3) + (2, 1) 이라고
생각할 수도 있기 때문이다.
그럼 Sum[2][2]의 값은 얼마일까 ?? Sum[2][2] 또한, (1, 1) + (1, 2) + (2, 1) + (2, 2) 를 한 '12'가 우리가 원하는 값이다.
그럼 이를 어떻게 계산해줘야 할까 ??
바로 "계산하고자 하는 좌표에서 왼쪽 좌표까지의 누적합과 위쪽 좌표까지의 누적합을 더하기" 해주면 된다.
Sum[1][2] 부터 다시 한번 해보자.
왼쪽 좌표까지의 누적합 = 1, 위쪽 좌표까지의 누적합 = 0 (위쪽 좌표 존재하지 않음.)
그럼 1 + 0 으로 1이된다. 이 값에 우리가 구하고자 하는 좌표 값인 MAP[1][2]의 값인 '2'를 더해주면 된다. 즉, 1 + 0 + 2 = 3 이 된다. Sum[2][1] 로 가보자. 왼쪽 좌표까지의 누적합 = 0 (왼쪽 좌표 존재하지 않음) , 위쪽 좌표까지의 누적합 = Sum[1][1] = 1
0 + 1 = 1. 이 값에다가 MAP[2][1]의 값인 '4'를 더해주면 5가 된다.
그럼 지금까지 Sum[1][1] = 1, Sum[1][2] = 3, Sum[2][1] = 5 라는 것을 알았다. 이제 Sum[2][2] 의 값을 구해보자.
왼쪽 좌표까지의 누적합 = Sum[2][1] = 5. 위쪽 좌표까지의 누적합 = Sum[1][2] = 3. 현재 좌표의 값 = MAP[2][2] = 5
5 + 3 + 5  = 13.
그럼 이제 눈으로 직접 세보자. 과연 (1, 1) + (1, 2) + (2, 1) + (2, 2) 의 값이 13인지 ! 직접 세보면 12라는 것을 알 수 있다.
왜 값에서 다르게 계산될까 ?? 왜냐하면 "중복된 값"이 발생하기 때문이다.
Sum[2][1]에는 (1, 1) + (2, 1) 이 계산된 값이 들어있다.
Sum[1][2]에는 (1, 1) + (1, 2) 가 계산된 값이 들어있다.
두 개를 더하게 되면, (1, 1) + (2, 1) + (1, 1) + (1, 2) 가 된다. 즉 ! (1, 1)이 2번 중복되어서 계산되어진다.
따라서, 한번을 빼줘야 한다. 빼줘야 하는 좌표는 "왼쪽 대각선 위의 좌표" 이다.
(2, 2)를 계산할 때, (1, 1)이 2번 중복되었듯이, 나머지 좌표들에서도 왼쪽 대각선 위의 좌표가 중복될 것이다.
정리해보자면 (a, b)까지 존재하는 건포드의 갯수의 누적합 Sum[a][b] 의 값은
Sum[a][b] = Sum[a - 1][b] + Sum[a][b - 1] - Sum[a - 1][b - 1] + MAP[a][b] 가 된다 !
이 식을 통해서 본인은 맵의 모든 부분에 대한 누적합을 모두 구해주고 시작하였다.

이제 본격적으로 초콜릿을 잘라보자. 본인은 재귀와 메모이제이션을 이용해서 접근해 보았다.

재귀함수에 사용된 매개변수로는 4개의 변수를 사용해주었다.

(시작 x좌표, 시작 y좌표, 끝 x좌표, 끝 y좌표) 이렇게 4개의 변수를 사용해 주었다.

그리고 메모이제이션을 위해서는 4차원 int 형 배열을 하나 사용해 주었다.

Memo[][][][] 라는 변수를 사용해주었는데, Memo[a][b][c][d] = e 의 의미는

"(a, b)에서 (c, d)까지 초콜릿을 잘랐을 때, 지불해야 하는 최소 건포도의 갯수는 e개 입니다." 를 의미한다.

DFS함수 안의 내용을 구체적으로 알아보자.

우리에게 (시작 x좌표, 시작 y좌표), (끝 x좌표, 끝 y좌표) 가 주어진다면 크게 본다면 2가지 경우로 나눠서 생각할 수가 있다.

첫번째는 가로로 자르는 경우. 두번째는 세로로 자르는 경우 이다.

가로로 자른다면, 파랑색 선들 처럼 자를 수 있을 것이고, 세로로 자른다면 초록색 선들처럼 자를 수 있을 것이다.

그런데 어느 선으로 짤랐을 때 최소가 되는지를 구해야 한다. 본인은 이 부분을 모두 구해서 비교해 주었다.

먼저 가로만 보게 된다면 시작 x ~ 끝 x 까지의 범위가 주어지게 된다.(y는 어차피 일정한 값.)

그럼 이 범위를 2개의 범위로 나눌 수가 있다. (시작x ~ 시작x + A) , (x + A ~ 끝 x) 이런식으로 !!

세로도 마찬가지이다. 시작 y ~ 끝 y 라는 범위를 2개의 범위 (시작y ~ 시작y + A), (y + A ~ 끝 y) 이런식으로 !

코드로 나타내면 다음과 같이 구현할 수 있다.

for (int i = x; i < Ex; i++)
{
    int Result1 = DFS(x, y, i, Ey);
    int Result2 = DFS(i + 1, y, Ex, Ey);
    Memo[x][y][Ex][Ey] = Min(Memo[x][y][Ex][Ey], Result1 + Result2 + Current_Sum);
}
for (int i = y; i < Ey; i++)
{
    int Result1 = DFS(x, y, Ex, i);
    int Result2 = DFS(x, i + 1, Ex, Ey);
    Memo[x][y][Ex][Ey] = Min(Memo[x][y][Ex][Ey], Result1 + Result2 + Current_Sum);
}

(x, y)가 시작점이고 (Ex, Ey)가 끝점을 의미한다. 그렇다면 (x, y) ~ (Ex, Ey)라는 범위를 위에서 말했듯이 2가지 범위로

나누는 것이다. 그 2가지 범위로 나누는 것은 for문으로 모두 하나하나 다 나눠 보았다.

그렇다면 여기서 ! 우리가 위에서 구해놓은 누적합에 대해서 또 다른 이야기를 한번 해야한다.

우리는 이런 맵에서 누적합에 대해서 위에서 구해놓았다. 그런데 지금은 조금 상황이 반대이다. 특정 부분에 대한

누적합만 구해야 한다. 즉 ! 우리가 구해놓은 누적합에서 일부분을 뺀 누적합만을 구해야 한다. 왜냐하면 우리는 초콜릿을

자르기 시작했고 자르면서 다음과 같은 상황이 발생하기 때문이다.

이렇게 잘랐다면 (1, 2)에서 (2, 3)까지의 누적합을 알아야 지불해야 하는 건포도 수를 알 수 있기 때문이다.

만약 Sum[2][3]를 구한다면 ? 이는 (1,1)에서부터 누적합인 21이 저장되어 있을 것이다. (1, 2)에서부터 누적합이 아니다 !

이 부분을 구하는 것도 위에서 Sum을 구한 공식과 비슷하다. 위에 그림 말고 3x3짜리 맵으로 알아보자.

본인이 직접 위의 맵에 대한 누적합을 구해봤더니 다음과 같다.

그럼 시작(x, y)를 (2, 2)로 가정하고, 끝점(x, y)를 (3, 3)으로 가정해보자. 즉 우리가 구해야 할 누적합의 부분은 다음과 같다.

우리는 빨강색 부분에 대한 누적합을 구하고 싶다면 역으로 생각하면 이렇게 생각할 수 있다.

우리가 기존에 구해놨던 (3, 3)에 대한 누적합(18)에서 아래와 같이 노랑색으로 칠한 부분에 대한 누적합을 빼는 것으로

생각할 수가 있다.

이 부분을 빼버리면 된다. 그런데 우리는 이미 파랑색 점에 대한 누적합과 초록색 점에 대한 누적합을 알고 있다.

왜냐하면 파랑색 누적합은 Sum[3][1]의 값이고, 초록색 점의 누적합은 Sum[1][3]의 값을 가지고 있다.

즉, (2, 2)에서 (3, 3)에 대한 누적합을 구하고 싶다면, Sum[3][3]에서 Sum[1][3]과 Sum[3][1]의 값을 빼면 된다.

갑자기 너무 뜬금없는 숫자들만 나온 것 같다. 이제는 식으로 이해해보자.

현재 (x, y) = ( 2, 2)이고, (Ex, Ey) = (3, 3)이다. 그런데 빼야 하는 부분은 (1, 3)과 (3, 1) 이다.

즉, 빼야 하는 부분은 (x - 1, Ey) , (Ex, y - 1)에 대한 누적합 부분이 된다.

그대로 대입해보면 (2 - 1 , 3), (3 , 2 - 1) = (1, 3), (3, 1)이 나오게 된다. 그럼 정말로 이게 맞는지 한번 확인해보자.

위에서 구해놓은 누적합이다. (2, 2)에서 (3, 3)까지의 누적합을 계산해보면 2 + 2 + 3 + 3 = 10이 나오게 된다.

위의 식대로 구해본다면 Sum[3][3] - Sum[1][3] - Sum[3][1] 이니까, 18 - 6 - 3 = 9 가 나오게 된다.

이번에도 값이 다르게 나온다. 왜 그럴까 ??? 풀어써보면 중복이 나온다는 것을 쉽게 알 수 있다.

Sum[1][3] = (1, 1) + (1, 2) + (1, 3)

Sum[3][1] = (1, 1) + (2, 1) + (3, 1)

딱 봐도 (1, 1)이 중복되서 2번 빠져버렸다는 것을 알 수 있다. 즉 ! (1, 1)을 한번 다시 더해줘야 한다는 것인데, (1, 1)은

식으로 어떻게 구할까? 바로 (x - 1, y - 1)의 좌표이다.

마지막으로 정리해보자.

시작점이 (x, y)이고 끝점이 (Ex, Ey)라고 가정했을 때, (x, y) ~ (Ex, Ey)에 대한 부분 누적합은

Sum[Ex][Ey] - Sum[x - 1][Ey] - Sum[Ex][y - 1] + MAP[x - 1][y - 1] 이 된다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 55
#define INF 2e9
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
int Sum[MAX][MAX];
int Memo[MAX][MAX][MAX][MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Initialize()
{
    memset(Sum, 0, sizeof(Sum));
    memset(Memo, -1, sizeof(Memo));
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Calculate_Sum()
{
    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] + MAP[i][j];
        }
    }
}
 
int DFS(int x, int y, int Ex, int Ey)
{
    if (x == Ex && y == Ey) return 0;
    if (Memo[x][y][Ex][Ey] != -1) return Memo[x][y][Ex][Ey];
 
    Memo[x][y][Ex][Ey] = INF;
    int Current_Sum = Sum[Ex][Ey] - Sum[x - 1][Ey] - Sum[Ex][y - 1] + Sum[x - 1][y - 1];
    for (int i = x; i < Ex; i++)
    {
        int Result1 = DFS(x, y, i, Ey);
        int Result2 = DFS(i + 1, y, Ex, Ey);
        Memo[x][y][Ex][Ey] = Min(Memo[x][y][Ex][Ey], Result1 + Result2 + Current_Sum);
    }
    for (int i = y; i < Ey; i++)
    {
        int Result1 = DFS(x, y, Ex, i);
        int Result2 = DFS(x, i + 1, Ex, Ey);
        Memo[x][y][Ex][Ey] = Min(Memo[x][y][Ex][Ey], Result1 + Result2 + Current_Sum);
    }
 
    return Memo[x][y][Ex][Ey];
    
}
 
void Solution()
{
    Calculate_Sum();
    Answer = DFS(1, 1, N, M);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}