https://www.acmicpc.net/problem/11873
11873번: 최대 직사각형
입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두
www.acmicpc.net
https://6epsilon.tistory.com/14
백준 3321 가장 큰 직사각형
https://www.acmicpc.net/problem/3321 3321번: 가장 큰 직사각형 열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열) www.acmicpc.net n개의
6epsilon.tistory.com
에서 만들었던, 각 행에서 각 위치에 대해 위로 연속한 1의 개수를 구한다. 이제 각각의 줄에서 히스토그램에서 가장 큰 직사각형을 찾는 유명한 문제를 풀면 된다. 그러면 이 부분의 구현에 따라 O(nmlogm)이나 O(m)에 처리할수 있다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1772 정원 정리 (0) | 2023.02.09 |
|---|---|
| 백준 6181 플러드 필 (Flood Fill) (0) | 2023.02.07 |
| 백준 1733 등번호 (0) | 2023.02.03 |
| 백준 25257 Monty's Hall (0) | 2023.02.01 |
| 백준 14458 소가 길을 건너간 이유 10 (2) | 2023.02.01 |
