티스토리 뷰

Coding Test/알고스팟

[C++] 알고스팟/분할정복 - 울타리 잘라내기

Junchoi 2020. 3. 31. 16:05

문제링크

https://algospot.com/judge/problem/read/FENCE

 

algospot.com :: FENCE

울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대

algospot.com

 

아래 그림과 같이 높이가 제각각으로 붙어있는 나무 판자에서 가장 넓은 직사각형을 구하는 문제입니다.

 

 

브루트포스로 가능한 모든 값을 탐색해도 답을 얻을 수는 있지만 시간안에 구하지는 못하므로 분할정복을 사용해 문제를 풀어야합니다.

 

먼저 판자를 아래와 같이 절반으로 나눠 양쪽에서의 가장 넓은 사각형을 구합니다.

 

왼쪽과 오른쪽 중 더 넓은 값을 구했다 하더라도 전체 판자 중 가장 큰 사각형이 아닐 수 있습니다.

양쪽에 모두 걸친 사각형이 나올 수 있기 때문입니다.

따라서 양쪽 모두 걸친 중간을 기준으로 시작하여 더 넓은 사각형이 있는지 탐색해 나갑니다.

 

 

구현 코드

 

'Coding Test > 알고스팟' 카테고리의 다른 글

[C++] 알고스팟/동적계획법 - 외발 뛰기  (0) 2020.08.15
[C++] 알고스팟/분할정복 - 팬미팅  (0) 2020.08.09
[C++] 알고스팟/분할정복 - 쿼드 트리 뒤집기  (0) 2020.03.30
[C++] 알고스팟/비트마스크 - 졸업 학기  (0) 2020.03.29
[C++] 알고스팟/완전탐색 - Synchronizing Clocks  (0) 2020.01.18