1915_가장 큰 정사각형

Concept & Idea

다이나믹 프로그래밍적으로 사고하는 것은 맞았다.
내가 i,j에 위치해있을 때, [i-1][j-1], [i][j-1],[i-1][j]를 검사하는 것이 중요했다.
처음에는 max값으로 잡았는데, min값으로 잡아야 했었다.
min으로 잡고나니 또 다른 문제가 발생했었는데, dp배열을 내가 계속 갱신해주고 있었던 것이 문제였다.

dp[i][j]=t; dp[i-1][j-1]=t; dp[i][j-1]=t; dp[i-1][j]=t;

이 작업을 생략하고, 그냥 dp[i][j]=t 를 해주니 맞았다.

Code

#include <iostream>
#include <string>
using namespace std;
string map[1001];
int dp[1001][1001];
int n,m;
int res=0;
int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        cin>>map[i];
    }
    for(int i=0; i<n; i++) {
        for(int j=0; j<m; j++) {
            if(map[i][j]=='1') {
                if(res<1)
                    res=1;
                dp[i][j]=1;
                if(i-1>=0 && j-1>=0) {
                    if(dp[i-1][j-1]!=0 && dp[i][j-1]!=0 && dp[i-1][j]!=0) {
                        int t=0;
                        if(dp[i-1][j-1]==dp[i][j-1] && dp[i-1][j]==dp[i-1][j-1] && dp[i][j-1] == dp[i-1][j-1]) {
                            t=dp[i-1][j-1]+1;
                        } else {
                            t=min(min(dp[i-1][j-1], dp[i][j-1]), dp[i-1][j])+1;
                        }
                        dp[i][j]=t;
                        if(res<t)
                            res=t;
                    }
                }
            }
        }
    }
    cout<<res*res<<endl;
}

 

Fealing

그래도 사고하는 것은 맞아서 다행이다.
좋은 문제였던 것 같다.