[BOJ] 1915. 가장 큰 정사각형

https://www.acmicpc.net/problem/1915

접근 방법

정사각형이 되는 경우를 생각해보았다.

• 현재 꼭짓점(x,y)에서 (x-1,y) (x,y-1) (x-1,y-1)이 모두 true라면 정사각형이다.

처음에는 재귀적으로 호출을 해서 정사각형을 체크하려 해주었음

• 당연히 시간 초과...

어떻게 하면 체크 한 것을 가지고 있으면서 정사각형이 최대가 되는지에 대한 생각...

• index는 11000, 11000이 모두 고정적이다. → 메모지에이션을 쓰면 되지 않을까?

동적프로그램을 생각해보았다.

위, 왼쪽, 왼쪽위 대각선이 모두 1일 경우

위, 왼쪽, 왼쪽위 대각선의 최소값에 +1을 더한값이 가장 큰 정사각형이 된다.

1. 위, 왼쪽, 왼쪽위 대각선이 1일 경우

cache[i][k] = max( cache[i-1][k], cache[i-1][k-1], d[i][k-1]) + 1이 된다.

2. 위, 왼쪽, 왼쪽위 대각선이 0이 포함된 경우

map[i][k]가 true이면 d[i][j] 는 1

map[i][j]가 false이면 d[i][j] 는 0 이 된다.

예시

---

Need Know

1. DP

전체 코드 ( Java )

import java.io.*;
import java.util.StringTokenizer;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int M;
    static boolean[][] map;
    static int[][] cache;
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        bw.flush();
        bw.close();
        br.close();
    }
    static void set() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new boolean[N+1][M+1];
        cache = new int[N+1][M+1];
        for(int i=1; i<N+1; i++){
            String str = br.readLine();
            for(int k=1; k<M+1; k++){
                map[i][k] = str.charAt(k-1) == '1' ;
                if(map[i][k]) cache[i][k] = 1;
            }
        }
    }
    static void solve() throws IOException {
        for(int i=1; i<N+1; i++){
            for(int k=1; k<M+1; k++){
                if(map[i-1][k] && map[i-1][k-1] && map[i][k-1]){
                    int temp = Math.min(cache[i-1][k], cache[i-1][k-1]);
                    cache[i][k] = Math.min(temp,  cache[i][k-1]) + 1;
                }
                ans = Math.max(cache[i][k], ans);
            }
        }
        bw.write(ans*ans+"");
    }
}