답만 보려면 클릭

문제

i: 행 번호 j: 열 번호 arr[i][j]: 입력 받은 n * m 배열 dp[i][j]: (i, j)위치를 오른쪽 아래 꼭지점으로 하는 가장 큰 정사각형의 한 변의 길이

점화식은 이렇다.

if (arr[i][j] == 1) 
dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;

(i, j)에서의 정사각형의 한 변의 길이의 최대값은 왼쪽, 위, 왼쪽 위 대각선 방향의 dp값 중 최소값에 1을 더한 값이다.

일단 arr[i][j] == 0이면 dp[i][j] == 0 이다.

dp[i][j-1],dp[i-1][j-1], dp[i-1][j]를 가지고 dp[i][j]를 유추하는 시나리오를 생각해보자.

dp[i][j]를 (i, j) 위치를 오른쪽 아래 꼭지점으로 하는 가장 큰 정사각형의 한 변의 길이로 정했다. 이 값을 구하기 위해서는 (i, j) 위치로 이전의 정사각형을 확장시킬 수 있는지 판단해야 한다.

정사각형을 구성하려면 4개의 위치(위, 왼쪽, 대각선 위쪽, 그리고 자기 자신)에서 연속된 1이 필요하고 4개 중 어느 하나라도 1이 아니면 확장할 수 없다(그림 그려가면서 해보셈)

구체적으로, (i, j) 위치를 포함한 정사각형으로 확장하려고 할 때 dp가 dp[i-1][j-1] = 2, dp[i-1][j] = 1, dp[i][j-1] = 3인 상황이라 가정해보자. 이것은 arr 에서는 다음과 같다.

초록 박스가 dp[i][j-1] 즉 (i, j-1) 에서의 최대 변 길이, 파랑은 (i-1, j-1), 파랑+노랑이 (i-1, j)에서의 최대 변 길이를 각각 나타낸다.

정사각형의 확장은 가로, 세로 모두 1씩 이루어져야 하는데 (i, j)로 확장하려 할 때 각 박스가 자신의 가로(세로) 길이 + 1만큼씩만 확장을 허용한다. 초록 박스는 길이가 1이었으므로 1+1 = 2까지만 확장이 허용되는 것이다.

그럼 3개의 박스가 허용하는 최소치만큼 확장이 가능하기 때문에 dp[i][j]가 세 인접 값의 최솟값에 1을 더한 값이 되는것.