buildings > 문제은행

본문 바로가기


문제은행

1020 : buildings

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 40 회    시도횟수: 523 회   



"농부 창호는 자신의 소들을 데리고 한적한 도시에서 조금은 시끄러운 도시로 여행을 떠났다. 험난한 여정을 끝내고 도시에 도착했을 때 지평선에 펼쳐진 일출과 직사각형 형태의 빌딩의 실루엣들이 소들을 환영하고 있었다."

 

지평선위에는 N개의 빌딩이 서 있으며 길이는 유한하다고 하자. 각 빌딩의 실루엣은 지평선 바로 위에 위치 해 있으며 지평선 내에서의 정수의 가장 왼쪽과 오른쪽의 위치를 가지고 있으며 1이상의 높이를 가지고 있다. 빌딩끼리는 서로 겹쳐서 위치 할 수 있으며 높이가 높은 빌딩이 다른 빌딩을 가려서 나타날 수 있다. 이에 대한 정보가 주어졌을 때 소들에게 보이는 빌딩의 넓이를 구하는 프로그램을 작성하라.


첫 번째 줄에는 빌딩의 개수 N(1≤N≤40,000)이 입력된다.
두 번째 줄부터 N+1 번째 줄은 빌딩의 실루엣에 대한 정보가 입력된다. i+1번째 줄은 i번째 빌딩의 정보가 입력되며 공백을 사이에 두고 Ai, Bi (1 ≤ Ai< Bi ≤ 1,000,000,000), Hi (1 ≤ Hi ≤ 1,000,000,000)가 입력되는데 이는 각각 빌딩의 맨 왼쪽 위치 맨 오른쪽 위치 그리고 높이를 뜻한다. 
또한 앞에서 언급 하였듯 빌딩의 실루엣은 직사각형의 형태로 이루어진다.


입력 받은 도시의 정보에 대해 보이는 실루엣의 넓이를 출력하라.

[Copy]
4
2 5 1
9 10 4
6 8 2
4 6 3
[Copy]
16


위의 예제를 그림으로 표현하면 아래와 같다.




USACO 2007 Open Silver, poj 3277

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.