목록2차원 DP (1)

Hello, Freakin world!

[백준 1915번][Java] 가장 큰 정사각형 - 2차원 배열, DP

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP 문제를 계속 풀고 있는데, 패턴이 참 다양하다는 생각이 듭니다. 그리고 꽤 재밌네요 ㅋㅋㅋ 핵심 아이디어는 위처럼 (i,j) 위치의 값이 1일 때 위, 왼쪽 위, 왼쪽 위치의 요소도 1이면 정사각형 만들어 진다에서 출발합니다. 나머지는 저 위의 아이디어를 기반으로 점화식을 작성하면 됩니다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java..
알고리즘/PS 2020. 10. 10. 22:23
Prev 1 Next