[백준 1915] 가장 큰 정사각형 [C]

백준 - 1915

---

풀이

dp[i][j]를 기준으로, dp[i][j-1], dp[i-1][j-1], dp[i-1][j]가 모두 0이 아닌 정수일 때, 이들의 최솟값에 1을 더한 값이

dp[i][j]를 기준으로 만들어지는 정사각형의 한 변의 길이이다.

5 x 5 정사각형

가장 큰 dp[i][j]값을 max에 담아, max의 제곱을 출력해주면 된다.

---

소스코드

#include <stdio.h>
int dp[1001][1001];
int min(int a, int b, int c){
    if (a < b && a < c) return a;
    return b < c ? b : c;
}
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%1d", &dp[i][j]);
            
    int max = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            if (dp[i][j]){
                dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1;
                max < dp[i][j] && (max = dp[i][j]);
            }
        }
    printf("%d", max*max);
}

---

출처

1915번: 가장 큰 정사각형