문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

Naive 하게, (r, c)에서 가능한 정사각형을 찾기 위해서는, 칸의 거리를 점차 늘려가며 조사하면 된다. 그러나, 이때, 다음 거리의 있는 칸에서 만들 수 있는 정사각형의 크기를 이미 알고 있으므로, 이것을 활용하면 불필요한 조사를 생략할 수 있다.

Algorithm

Dynamic Programming으로 푼다.
(n-1, m-1)에서 (0, 0)으로 bottom-up방식으로 iteration을 진행한다.
현재 칸이 (r, c)이고 1일 때, (r+1, c), (r, c+1), (r+1, c+1) 칸에서 만들 수 있는 정사각형의 최소 + 1이 현재 칸에서 만들 수 있는 최대 길이의 정사각형이다.

Data Struture

• dp[n][m]: 각 칸에서 만들 수 있는 정사각형의 최대 길이를 저장한다.

결과

Other

시간 복잡도는 O(nm)이다.