19151 [백준] 1915 가장 큰 정사각형 DP 문제 : www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 분석 : 대표적인 DP 문제로 1씩 더하는게 곧 정사각형의 한 변이 된다는 게 신기했다. DP가 전에 한번 공부했을 때 잘 이해가 안됐는데 이번에 조금 알거 같다는 생각이 들었다. 우선 arr이라는 원래 2차원 배열을 만들고 memo라는 배열에 값을 계산해 누적한다. arr[i-1][j-1], arr[i-1][j], arr[i][j-1] 모두가 1일때만이 arr[i][j]과 함께 정사각형을 만들 수 있으므로 그런 경우만 검사 한 뒤 1을 더해 한변을 memo 배열에 누적해.. 2021. 2. 5. 이전 1 다음