[백준] 1915 가장 큰 정사각형

1915번: 가장 큰 정사각형

 

boj.kr

풀이

이 문제는 동적 계획법을 사용해야한다. 이 문제의 핵심 아이디어는 위에서부터 탐색하면서 최대 크기의 정사각형을 갱신하는 것이다. 즉 dp[i][j] = (j, i)에서의 최대 정사각형의 길이가 된다. (수학에서 사용하는 좌표계를 기준으로 x, y 순으로 좌표를 표현했음을 참고할 것)

배열을 board[][]라고 하겠다.
그러면 board[i][j]가 1인 곳은 변의 길이가 1인 정사각형이다.
변의 길이가 2인 정사각형은 board[i][j], board[i-1][j], board[i][j-1], board[i-1][j-1]이 모두 1이어야 한다. 이 문제의 풀이는 여기서 힌트를 얻을 수 있다. 아래의 예시를 보면서 좀 더 알아보자.

(0, 0 ~ 3, 0), (0, 0) ~ (0, 3)은 아무리 큰 정사각형이 나와도 길이가 1이므로 (1, 1)부터 살펴보도록 하자. 

(0, 0), (0, 1)이 0이므로 (1, 1) 위치에서 최대로 만들 수 있는 정사각형은 1이 된다.

마찬가지로 (2, 1) 지점도 최대로 만들 수 있는 정사각형이 1이 된다. 나머지 1행은 마찬가지로 최대 크기가 1이다.

이번엔 (2, 2) 지점을 한번 살펴보자.

(1, 1), (1, 2), (2, 1)이 모두 최대 크기가 1인 정사각형이므로 (2, 2) 위치에서는 최대 크기가 2인 정사각형을 만들 수 있다. 따라서 board[2][2] = 2로 갱신해주면 된다.

이런식으로 모든 곳들을 탐색하다보면 규칙이 나온다. 규칙은 board[i][j] == 1 일 때 board[i][j] = board[i-1][j], board[i][j-1], board[i-1][j-1]의 최솟값 + 1 이 된다는 것을 알 수 있다. 아래의 코드는 (1, 1)부터 탐색을 시작하기 때문에 n과 m이 1인 경우에 답을 찾을 수 없어서 별도의 예외처리를 통해 해결해주었다.

코드

C++