백준 1028 다이아몬드 광산 혼내주기

 

 

삽질 1. dp인 줄 알았는데 설명하기도 어려운 방법으로 구현하려다 포기.
삽질 2. 도저히 안떠올라서 구글링을 통해 dp table에 현재 위치에서 뻗은 개수를 저장해야 함을 발견.
삽질 3. 최대 크기부터 유효한 범위에서 다이아몬드를 발견하면 바로 종료하도록 구현했는데, 시간 초과.

 

결국 크기를 dp table의 범위 내에서 정하고, 군데군데 가지치기를 넣어서 해결했다. 

 

너무 삽질을 오래해서 풀었는데도 기분이 꿀꿀하다. 아직도 갈 길이 멀다...

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int map[751][751];
int bl[751][751], br[751][751];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    string s;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> s;
        for(int j = 1; j <= m; ++j){
            map[i][j] = s[j-1] - '0';
        }
    }

    for(int i = n; i > 0; --i){
        for(int j = 1; j <= m; ++j){
            if(!map[i][j]) continue;
            bl[i][j] = bl[i+1][j-1] + 1;
            br[i][j] = br[i+1][j+1] + 1;
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!map[i][j]) continue;
            int mSize = min(br[i][j], bl[i][j]);
            if(mSize < ans) continue;
            for(int size = mSize; size > 0; --size){
                if(j - (size-1) < 1 || j + (size-1) > m || i + 2*(size-1) > n) continue;
                if(size < ans) continue;
                if(bl[i][j] >= size && bl[i+size-1][j+size-1] >= size && br[i][j] >= size && br[i+size-1][j-(size-1)] >= size){
                    ans = max(ans, size);
                    break;
                }
            }
        }
    }

    cout << ans;

}