목록다이나믹프로그래밍 (1)
Hello Ocean! 🌼
[백준/C++] 1915. 가장 큰 정사각형
문제 배열에서 1로 된 가장 큰 정사각형의 크기를 구해라! www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 DP를 이용하겠다! cache[r][c] = min(min(cache[r + 1][c], cache[r + 1][c + 1]), cache[r][c + 1])+1; cache배열에서 제일 아래 행, 오른쪽 열은 table과 똑같이 채워준다. 그 후에 반복문을 돌면서, table값이 0이면 0으로 채우고 넘어가고, 0이 아니면 아래 그림과 같이 cache[r + 1][c], cache[r + 1][c + 1], cach..
Algorithm
2021. 4. 14. 12:55