[백준 1915] 가장 큰 정사각형 (Gold IV)

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

1915번: 가장 큰 정사각형

 DP로 풀린다는 사실이 꽤 유명하다. dp[i][j]를 grid[0..i][0..j]에 존재하고 [i][j] 좌표를 차지하는 가장 큰 정사각형이라고 정의하자. 그러면 DP 식은 dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1이다. 이 점화식은 LCS나 knapsack 문제 풀 때처럼 테이블을 순차적으로 방문하면서 칸 채워넣기가 좋은 점화식이다. 시간복잡도는 O(mn)이다.

 

 또한 dp 저장공간 토글링 기법으로 공간복잡도 O(2m)만을 사용하는 풀이를 할 수 있다. 시간복잡도는 여전히 O(mn)이지만, 공간 할당하는 것도 다 오버헤드 비용이 들기 때문에 공간복잡도 최적화를 해주면 실행시간이 많이 단축되는 듯하다. 나는 8ms까지도 단축시킬 수 있었다.

#include <bits/stdc++.h>

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::string> data(n);
    for (auto &s : data) {
        std::cin >> s;
    }
    
    int ret = 0;
    std::vector<int> memo(m);
    for (int j = 0; j < m; ++j) {
        memo[j] = data[0][j] == '1';
        ret = std::max(ret, memo[j]);
    }
    
    for (int i = 1; i < n; ++i) {
        std::vector<int> temp(m);
        temp[0] = data[i][0] == '1';
        ret = std::max(ret, temp[0]);
        
        for (int j = 1; j < m; ++j) {
            if (data[i][j] == '0') {
                temp[j] = 0;
            } else {
                temp[j] = std::min(temp[j - 1], std::min(memo[j], memo[j - 1])) + 1;
                ret = std::max(ret, temp[j]);
            }
        }
        memo = std::move(temp);
    }
    
    std::cout << ret * ret << '\n';
}

#ifndef LOCAL
int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}
#endif