백준, BOJ, 1915번, 가장 큰 정사각형 : C++ [CPP]

감이 안잡히면 가장 어려운게 DP가 아닐까..

이것도 그렇다.

 

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

 

---

 

#맞는 풀이

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

int n, m;

int map[1001][1001];


int main() {
    cin >> n >> m;
    //최솟값
    int ans = 0;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++) {
            map[i][j] = s[j] - '0';
            //만약 1이 등장하면 최소 ans = 1
            if (map[i][j] == 1) ans = 1;
        }
    }

    //1,1부터 시작하므로 나머지에 대한 계산은 이미 ans에 넣어놔야함.
    // 위에서 1이 출현하면 최소는 1로 해두어서
    //아래와 같은 예외 방지
    // 3 3 
    // 0 0 0
    // 0 0 0
    // 1 0 0
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (map[i][j] == 1) {
                map[i][j] = min(min(map[i - 1][j - 1], map[i - 1][j]), map[i][j - 1]) + 1;
                ans = max(map[i][j], ans);
            }
        }
    }

    cout << pow(ans,2);


    return 0;
}

 

문자열 입력에 유의하자. 하나씩 받지를 못한다. getline을 써도 된다.

 

아무튼 DP는 해보면서 규칙을 찾아야 하는데.. 너무 어렵다..

나는 이러한 DP적 생각을 머리보다는.. 감으로 얻어야 겠다. 양치기 해야겠다.