반응형
가장 큰 정사각형
-
BOJ) 가장 큰 정사각형알고리즘/백준 2020. 8. 26. 15:22
가장 큰 정사각형 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 전에 푼 적이 있는 문제여서, 비교적 쉽게 풀 수 있었다. 당시에는 어떻게 풀어야하는지 막막했었는데, 그때 봤던 풀이가 아직 머릿속에 남아있었다. 우선, 맵을 돌면서 1인 경우에 좌측 상단, 좌측, 상단 세 군데를 확인한다. 세 곳의 최소값 +1(자기자신)이 dp의 값이 된다. dp[y][[x] += min(dp[y-1[[x-1], dp[y-1][x], dp[y][x-1]) 이 된다는 소리다. 변이 2인 사각형은 2로, 3을 만족하는 사각형은 3으로 값이 정해지는 것이다. (손으로 위의 식을 풀어가다보면 쉽게..