algospot.com :: FENCE
울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대
algospot.com
분할정복은 문제를 부분 문제로 뚝 자르고 잘라져서 나온 조각에 대해 똑같이 처음 했던 것처럼 뚝 자르기를 반복하여 정답을 찾아내는 방식인거같다.
다만 완전탐색과 조금 다른점이 있다면 문제마다 구현해야할 기저사례, 점화식을 깊게 생각해봐야하고, 이를 구현하는 것이 까다롭다는 것이다. 대강 원리는 이해했으니 문제를 많이 풀어보면서 문제 유형에 익숙해지고 구현력을 키워야겠다.
#include <iostream> #include <vector> using namespace std;
vector<int> fence; inline int max(const int a, const int b) { return a > b ? a : b; } inline int min(const int a, const int b) { return a < b ? a : b; } int Solution(int left, int right) { if (left == right) return fence[left]; int mid = (left + right) / 2; int ret = max(Solution(left, mid), Solution(mid + 1, right)); int lt = mid, rt = mid+1; int height = min(fence[lt], fence[rt]); ret = max(ret, height * 2);
while (left < lt || rt < right) { if (rt < right && (left == lt || fence[lt-1] < fence[rt+1])) { rt++; height = min(height, fence[rt]); } else { lt--; height = min(height, fence[lt]); } ret = max(ret, height * (rt - lt + 1)); } return ret; }
int main(void) { int testcase; cin >> testcase; while (testcase--) { int num, w; cin >> num; for(int i =0; i<num; i++) { cin >> w; fence.push_back(w); } cout << Solution(0,num-1) << endl; fence.clear(); } } |
알고리즘 200일 프로젝트 - 35day
'알고리즘 > algospot' 카테고리의 다른 글
| 알고리즘 문제해결전략 문제8.2 와일드카드 (ID: WILDCARD) (0) | 2020.05.25 |
|---|---|
| 알고리즘 문제해결전략 예제: 외발 뛰기 (ID: JUMPGAME) (0) | 2020.05.22 |
| 알고리즘 문제해결전략 문제7.2 쿼드 트리 뒤집기 (ID: QUADTREE) (0) | 2020.05.09 |
| 알고리즘 문제해결전략 문제6.8 시계 맞추기(ID: CLOCKSYNC) (0) | 2020.04.10 |
| 알고리즘 문제해결전략 문제6.5 게임판 덮기(ID: BOARDCOVER) (0) | 2020.04.09 |