이번에 풀어본 문제는
백준 1915번 가장 큰 정사각형 입니다.

📕 문제 링크

❗️코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int [][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        dp = new int[n + 1][m + 1];
        int answer = 0;

        for (int i = 1; i <= n; i++) {
            String input = br.readLine();
            for (int j = 1; j <= m; j++) {
                char c = input.charAt(j - 1);

                if (c == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }

        System.out.print(answer * answer);
    }
}

📝 풀이

주어진 배열에서, 가장 큰 정사각형의 넓이를 출력하는 문제입니다.
dp 배열을 활용하여 해결했습니다.
주어진 배열의 값이 0인 경우는 사각형을 완성할 수 없으므로 제외하고,
1인 경우에는 dp[i-1][j], dp[i][j-1], dp[i][j] 3가지 값중 가장 작은 값 +1 을 dp[i][j]에 담아줍니다.
그러면 dp 배열의 인덱스에 만들 수 있는 사각형의 길이를 누적할 수 있습니다.
마지막으로, 결괏값인 answer에 대해 제곱 연산으로 넓이를 구해주면 해결됩니다.