히스토그램 분할정복 (1) 썸네일형 리스트형 [백준/C++] 6549번 히스토그램 분할정복 증명 일단 그리디 하게 풀어서는 문제의 정답을 구할 수 없고, dp로 풀기에는 배열의 크기가 압도적으로 모자란 것으로 확인했다. HTML 삽입 미리보기할 수 없는 소스 그래서 분할 정복으로 왼쪽 오른쪽 나눠서 진행하면 어떨까? 하는 생각을 하게 되었지만, 각각 방향에서 최댓값은 찾을 수 있으나 다른 방향을 걸쳐서(가운데 부분에서) 최댓값을 구하는 경우면 어떻게 하나 고민하게 되었다. 고민 결과 아래와 같은 이유로 가운데가 포함된 경우 그리디 하게 모든 직사각형을 가져가는 것이 맞다고 생각하게 되었다. Prove 가운데가 포함된 직사각형에서 더 큰 방향의 막대를 포함하여 크기를 계산하면 최댓값을 구할 수 있다. Basis 가운데 막대가 포함된 경우에서 최댓값이 있다고 가정한다. 가운데를 제외한 왼쪽 부분의 최댓.. 이전 1 다음
