[BOJ] #1915 가장 큰 정사각형

https://www.acmicpc.net/problem/1915

---

배열의 인근을 탐색하며 정사각형이 되는 영역을 판별한 후, DP 배열에 저장하며 가장 큰 넓이 값을 출력해야하므로 계속 초기화 시켜주며 해결하면 된다.

사실 DP문제 대부분이 그렇듯 맨 처음에 점화식을 도출하는것이 가장 어려운 법인데, 이 문제 또한 그렇다. 난이도가 골드4인 문제라 DP 이외에 다른 스킬이나 알고리즘이 들어가지는 않고 점화식 자체만 잘 세울수 있으면 쉽게 해결할 수 있을것이다.

 

문제 예제에서 나온 입력값을 그대로 주었을때, 2차원 배열은 다음과 같이 구성된다. 이때, 0인 원소는 패스하고 1인 원소에 대해 DP를 수행한다.

arr[1][1]의 왼쪽, 왼쪽위, 위를 각각 L, LT, T라고 가정하고, 노란색과 주황색의 영역이 둘 다 1 1이 되는 케이스만 정사각형이 성립되므로 DP 배열에 넣고 maxLen 또한 초기화 시킨다. 해당 과정을 원소가 1인 모든 배열 인덱스에 대해 순회하며 수행하면, 가장 큰 정사각형의 길이를 구할 수 있다.

문제에서는 해당 정사각형의 넓이를 요구했으므로, cmath 헤더의 pow() 함수를 통해 거듭제곱을 구해준다. (그냥 maxLen * maxLen해도 상관없다.) 

 

문제에서의 최종적인 점화식은 다음과 같다.

dp[i][j] = min( min( dp[ i ][ j-1 ] , dp[ i-1 ][ j-1 ] ) , dp[ i-1 ][ j ] )    // dp배열 인덱스 구하는 점화식
maxLen = max( maxLen , dp[i][j] )    // 가장 큰 정사각형 길이를 최신화 시켜주는 시퀀스

---