목록백준 히스토그램에서 가장 큰 직사각형 (1)
어흥
[백준 6549] 히스토그램에서 가장 큰 직사각형 (C++)
문제 링크: https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 1. 주의할 점 - 분할정복 + 세그먼트 트리를 통해 해결한다 2. 구현 - 직사각형의 높이에 대한 정보를 Arr[] 배열에 담는다 - Tree[] 배열을 동적할당한다 - Init() 배열을 통해 Tree[] 배열에 최소 높이를 가지는 인덱스 번호를 저장한다 - findMinIdx() 함수를 통해 Left~Right까지의 Arr..
알고리즘/백준
2021. 5. 18. 18:53