백준 1915번 가장 큰 정사각형

< 백준 1915번 가장 큰 정사각형 - 마포 코딩박 >

사용한 알고리즘: DP


 NxM 그리드가 주어졌을 때 1로 이루어진 최대 정사각형을 구하는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 9~10)
 'dp[x][y] : (x,y) 을 오른쪽 모서리로 하는 최대 정사각형의 한변의 길이' 라고 설정했습니다.

(2) (코드 17~30)
 그리드를 (0,0), (0,1), ... , (N-1,M-1) 순으로 방문해 보면서 dp 값을 구해줍니다.
 dp[x][y] 를 구하기 위해서는 이전에 구해놨던 dp[x-1][y-1], dp[x][y-1], dp[x-1][y] 중 작은값에 +1 해주면 됩니다. 즉, (x,y) 를 오른쪽 모서리로 하고, (x,y) 를 기준으로 왼쪽 대각선, 왼쪽, 오른쪽 으로 얼마나 갈 수 있는지를 생각해주면 됩니다.