티스토리 뷰
오늘의 문제!
https://www.acmicpc.net/problem/1725
입력
첫째 줄에 N이 주어짐
둘째 줄부터 N개 동안 히스토그램의 높이가 주어진다
풀이
라이님의 분할정복에서 분할정복의 이해를 위해 예제로 설명해주신 문제였다
기본적인 풀이법은 여기에서 설명한 것과 비슷하다
1번 mid를 기준으로 왼쪽 중 최대 넓이가 나오는 경우
2번 mid를 기준으로 오른쪽 중 최대 넓이가 나오는 경우
3번 mid를 기준으로 왼쪽과 오른쪽이 겹쳐서 최대 넓이가 나오는 경우
소스
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <stdio.h> #include <iostream> using namespace std; int H[100000]; int calRectArea(int s, int e){ //넓이 반환 if(s==e){ // 가로: 1 높이: H[S] return H[s]; } int mid = (s+e)/2; int area = max(calRectArea(s,mid),calRectArea(mid+1,e)); int h = H[mid], l = mid, r = mid; while(l>s || r<e){ int p = l>s ? H[l-1] : -1; //왼쪽으로 확장 높이 int q = r<e ? H[r+1] : -1; //오른쪽으로 확장 높이 if(p>q){ //왼쪽으로 확장 h = min(h, p); l--; } else{ //오른쪽으로 확장 h = min(h,q); r++; } area = max(area, h*(r-l+1)); } return area; } int main(void){ int N; cin >> N; for(int i=0;i<N;i++){ cin >> H[i]; } cout << calRectArea(0,N-1); return 0; } | cs |
'PS > 백준' 카테고리의 다른 글
[백준/C++] 2339번 - 석판자르기 (0) | 2021.03.25 |
---|---|
[백준/C++] 1992번 - 쿼드트리 (0) | 2021.03.23 |
[백준/C++] 2104번 - 부분배열 고르기 (0) | 2021.03.19 |
[백준/C++] 1629번 - 곱셈 (0) | 2021.03.18 |
[백준/C++] 1493번 - 박스 채우기 (0) | 2021.03.17 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 분할정복
- Swift
- HumanInterfaceGuidelines
- 부스트코스
- 알고리즘
- Human Interface Guidelines
- HIG
- apple
- 싱글톤
- 온라인저지
- Firebase
- 디자인패턴
- UIView
- storage
- MVC
- 백준
- 오토레이아웃
- Human Interface Guideline
- ios
- DP
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
글 보관함