[BaekJoon/백준] 14925번 목장 건설하기

1시간 붙잡다가, 못 풀 것 같아서 다른 사람들의 풀이를 참고한 뒤 풀었다.

https://leesh111112.tistory.com/357

https://comyoung.tistory.com/205

 

 

이 문제를 연구소 문제처럼 푸려는 분도 있는데, 범위가 크기 때문에 절대 불가능하다.

#include <iostream>
#define MIN(a, b) ((a<=b)?a:b)

using namespace std;


int N, M;

int MAP[1001][1001];
int DP[1001][1001]; // 여유공간 1을 둔다. ( 맨 첫 위치를 1,1로 잡아서 dp에서 대각선 왼쪽 위를 봐도 문제없게 )

int MAX;

int main() {
    
    
    cin >> N >> M;
    
    
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= M; j++)
            cin >> MAP[i][j];
    }
    
    
    
    for(int i = 1; i <= N; i++) {
        
        for(int j = 1; j <= M; j++) {
            
            if(MAP[i][j] > 0)
                continue;
            
            DP[i][j] = MIN(MIN(DP[i - 1][j], DP[i][j - 1]), DP[i - 1][j - 1]) + 1;
            
            if(MAX < DP[i][j])
                MAX = DP[i][j];
            
        }
    }
    
    cout << MAX << "\n";
    
}

 

 

소요 시간 : 2시간