[ 백준 5463 ] 건포도 (C++)

백준의 건포도(5463) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

SWExpertAcademy의 초콜릿과 건포도(9282 / D4) 문제와 동일한 문제입니다.

초콜릿과 건포도 문제에 대한 풀이는 아래의 링크를 타고 확인할 수 있습니다.

[ 초콜릿과건포도(9282 / D4) Solution ]

문제가 동일하니 설명은 위의 글로 대체하겠습니다.

다만, 입력받은 부분이 SWEA 환경과 다르니 소스코드는 첨부해 놓겠습니다.

[ 소스코드 ]

#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 Input()
{
    memset(Memo, -1, sizeof(Memo));
    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 Cur_Cost = 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 + Cur_Cost);
    }
    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 + Cur_Cost);
    }
 
    return Memo[x][y][Ex][Ey];
}
 
void Solution()
{
    Calculate_Sum();
    Answer = DFS(1, 1, N, M);
}
 
void Solve()
{
    Input();
    Solution();
    cout << Answer << endl;
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}