728x90 DP:1 [python] 백준 1915 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 해결 가장 큰 정사각형의 크기를 구하는 것이기 때문에 DP를 이용하는 것이 좋다. (i,j) 좌표를 끝으로 하는 가장 큰 정사각형은 (i-1,j-1) 좌표를 끝으로 하는 가장 큰 정사각형 크기에 영향을 받는다. DP를 가장 큰 정사각형의 한 변의 길이라고 하면 DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) +1 이 될 것이다. CODE import sys input = sys.stdin.readline n, m =.. 2023. 3. 12. 이전 1 다음 728x90
