반응형 1725 썸네일형 리스트형 [BOJ 1725] 히스토그램 1725번 (히스토그램) 위의 문제는 분할 정복 알고리즘을 이용해서 해결할 수 있다. 분할 정복은 주어진 문제를 부분 문제들로 나누어 푸는 것이기 때문에 이 문제 또한 히스토그램을 나누어 푸는 것이 핵심이다. 따라서 주어진 n개의 막대그래프를 절반으로 나누게 되면 결국 찾고자 하는 가장 큰 직사각형은 다음 세가지중 하나에 속하게 된다. 1. 왼쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 2. 오른쪽 부분 문제에서 가장 큰 직사각형이 존재하는 경우 3. 가장 큰 직사각형이 왼쪽 부분 문제와 오른쪽 부분 문제에 걸쳐 있는 경우 1번과 2번의 경우에는 재귀 호출을 이용하면 되고, 3번의 경우만 특별히 고려한다면 답을 구할 수 있을 것이다. 문제에서 출력이 20억을 넘지 않는다고 하였으니, 변수 자료형을.. 이전 1 다음
