BOJ #6198 옥상 정원 꾸미기

문제 원본 : https://www.acmicpc.net/problem/6198

6198번: 옥상 정원 꾸미기

출처 : USACO 2006 November 2006 Contest Silver 1번

 

정답 소스코드

풀이법은 다음과 같습니다.

현재 확보된 시야를 저장할 배열을 선언합니다. (본문에서 int형 배열 build)

입력받을 빌딩의 개수를 저장한 후 각 빌딩의 높이를 입력받습니다.

그 후 lower bound를 이용하여 수정된 시야를 저장합니다. (본문에서 int형 배열 last)

이 때 일반적인 lower bound가 아닌 compare를 정의하여 역방향으로 확인하는 lower bound를 사용합니다.

수정된 시야에 위치한 높이로 build 배열의 값을 업데이트합니다.

lower bound로 last를 업데이트 한 후 바뀐 last들을 모두 합하면 정답을 얻을 수 있습니다. (본문에서 int형 변수 tot)

 

p.s. 위와 같이 lower bound를 이용한 풀이 말고 stack을 이용한 풀이도 있습니다.