문제 링크입니다: https://www.acmicpc.net/problem/6198
6198번: 옥상 정원 꾸미기
문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다. i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다. 그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다. 예) N=6, H = {10, 3, 7,
www.acmicpc.net
스택을 이용하는 문제였습니다.
1. 스택의 top에 위치한 빌딩의 높이가 i 번째 빌딩의 높이보다 작거나 같을 경우 i 번째 빌딩의 옥상을 볼 수 없으므로 스택의 top이 i 번째 빌딩의 높이보다 높을 때까지 pop을 해줍니다.
2. 스택에 i 번째 빌딩의 높이를 push 해줍니다.
3. i 번째 빌딩을 제외한 나머지 빌딩들이 i 번째 빌딩의 옥상을 볼 수 있으므로 결과에 (스택의 크기 - 1)을 더해줍니다.
* 주의: 결과의 자료형은 long long 형이여야합니다. N이 80,000이고 빌딩의 높이들이 동일하지 않은 상태에서 내림차순으로 주어진다면 정답이 int 형의 범위를 벗어나기 때문입니다.
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
| 백준 2525번 오븐 시계 (0) | 2020.03.13 |
|---|---|
| 백준 18258번 큐 2 (0) | 2020.03.11 |
| 백준 11978번 Mowing the Field (Bronze) (0) | 2020.03.08 |
| 백준 3079번 입국심사 (0) | 2020.03.08 |
| 백준 10868번 최솟값 (0) | 2020.03.08 |