백준(BOJ) 14921 용액 합성하기 **

#DP

지저분하게 코딩이 되었지만 어렵지 않은 디피문제

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 1005
#define INF 987654321
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

int n,m,ans=0,arr[MAX][MAX],dp[MAX][MAX];

int fun(int y,int x)
{
    int ret=dp[y][x];
    while(y+ret<=m&&x+ret<=n)
    {
        for(int i=y;i<=y+ret;i++)
            if(arr[i][x+ret]!=0)
                return ret-1;
        for(int i=x;i<=x+ret;i++)
            if(arr[y+ret][i]!=0)
                return ret-1;
        ret++;
    }
    return ret-1;
}

int main()
{
    fill_n(&arr[0][0],MAX*MAX,1);
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int k=1;k<=n;k++)
            scanf("%d",&arr[i][k]);
    for(int i=1;i<=m;i++)
        for(int k=1;k<=n;k++)
        {
            int tmp=0;
            if(arr[i][k]==0)
                tmp=fun(i,k)+1;
            ans=max(ans,tmp);
            if(dp[i][k]<tmp)
            {
                for(int p=0;p<tmp;p++)
                    for(int q=0;q<tmp;q++)
                    {
                        int len=min(tmp-p,tmp-q);
                        dp[i+p][k+q]=dp[i+p][k+q]<len?len:dp[i+p][k+q];
                    }
            }
        }
    printf("%d",ans);
}