[백준] No.1915 - 가장 큰 정사각형 (C++)

문제

www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

 

풀이

 다이나믹 프로그래밍 문제이지만 메모이제이션을 적용할 방법이 떠오르지 않아 답을 봐버렸다...

 

해당 문제는 (r,c)위치가 1이라면 (r-1,c-1), (r-1,c), (r,c-1)위치를 확인하여 가장 작은 값 +1이 (r,c)에서의 가장 큰 정사각형의 변의 길이이다. 즉, 해당 위치를 오른쪽 아래 모서리로 삼는 가장 큰 정사각형의 길이를 저장한다. 

이러한 연산을 모든 배열 값에 대해 실행해주면 이전의 값을 사용하여 빠르게 답을 구할 수 있다.

 

아래와 같은 예제로 예를 들어보자.

 

첫 번째 행과 열에서 끝나는 정사각형은 최댓값이 1이기 때문에 r=1, c=1에서부터 배열을 순회한다.

(1,1)에서는 (r-1, c-1), (r-1, c), (r, c-1)의 최솟값이 1이기 때문에 2가 된다. 계속 순회하여 (2,2)에서는

(r-1,c-1), (r-1,c), (r,c-1)의 최솟값이 2이기 때문에 3의 값을 갖는다.

최종 값은 아래와 같다.

 

우리는 배열을 순회하여 연산된 값의 최댓값의 제곱을 출력해주면 된다.

 

이때 배열의 크기가 2보다 작은 경우, 혹은 첫 번째 행과 열에서 1이 존재하지만 나머지가 모두 0일 경우 최댓값이 0으로 계산될 수 있으므로 배열에 1이 존재한다면 미리 max_length를 1로 대입해준다.

 

코드