15773번 - Touch The Sky 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 1158 | 293 | 219 | 27.969% |
문제
사진: 풍선으로 하늘에 띄운 집. 2018 KAIST RUN Spring Contest 포스터에도 사용된 사진이다.
서기 2117년, 유재민 교수에 의해 TSP (Traveling Salesperson Problem)의 선형시간 알고리즘이 개발되었다. 얼마 가지 않아 모든 컴퓨터 시스템은 붕괴되었고, 세상은 핵무기로 인해 황폐화 되었다. 컴퓨터 과학의 최고 전문가이던 당신 역시도 할 일을 잃게 되었고, 절망 속에 인생의 의미를 잃어버린 지 오래다. 과연 그동안 당신의 심장을 뛰게 하던 모든 것들은 어디로 갔을까? 끝없이 자신에게 질문한 끝에 내린 결론은...
"ICPC를 처음 시작한 그 때 그 카이스트를 가면, 내 인생의 의미를 찾을 수 있지 않을까?"
도로망이나 철도는 모두 황폐화된지 오래이다. 그렇지만 열렬한 ICPC 참가자였던 당신은 100년 전 대전 대회에서 받았던 풍선을 여전히 가지고 있다. 만약 그 풍선으로 집을 띄울 수만 있다면...
현재 당신에게는 N개의 풍선이 있고, 당신은 풍선을 하나씩 지붕에 매달아서 집을 하늘로 띄우려 한다. 각각의 풍선은 고도 제한 Li와 용량 Di가 있는데, 이는 기압의 영향으로 인하여 고도 Li 이하에서만 이 풍선을 불 수 있고, 이 풍선은 고도를 Di만큼 상승시킨 후 터진다는 것을 뜻한다.
당신의 여정은 고도 0에서 출발한다. 부풀어 있는 풍선이 2개 이상이면 집이 너무 빠른 속도로 상승할 수 있으니, 당신은 하나의 풍선을 불어서 지붕에 매단 후, 풍선이 터질 때가지 고도를 상승시키고, 터진 이후에 또 하나의 풍선을 불어서 터질 때까지 고도를 상승시키는 것을 반복해서 집을 띄울 예정이다. 편의상 터진 이후 풍선을 매다는 동안의 고도 변화는 없다고 가정한다. (즉, 풍선만이 유일하게 고도를 바꿀 수 있다.)
최종 고도는 어느 위치던 간에 상관 없으나, 하나의 풍선은 터지기 전 까지 일정한 거리를 움직일 수 있으니, 최대한 많은 풍선을 터뜨리는 것이 좋다. 고로 당신은 터뜨릴 수 있는 풍선의 최대 개수를 계산한 후, 정말 KAIST로의 여행을 떠날 수 있는지를 계산해 보려고 한다. 100년 전의 ICPC 경험이, 이 문제를 해결하는 데 정말 도움을 줄 수 있을까?
입력
첫 번째 줄에 풍선의 개수 N이 주어진다.
이후 N개의 줄의 i번째 줄에는 풍선의 고도 제한 Li와 풍선의 용량 Di를 의미하는 정수 2개가 공백으로 구분되어 주어진다.
출력
터뜨릴 수 있는 풍선의 최대 개수를 출력하여라.
제한
- 1 ≤ N ≤ 250,000
- 0 ≤ Li ≤ 1015
- 1 ≤ Di ≤ 109
서브태스크 1 (22점)
이 서브태스크는 다음의 조건을 만족한다.:
- N ≤ 20
서브태스크 2 (33점)
이 서브태스크는 다음의 조건을 만족한다.:
- N ≤ 5,000
서브태스크 3 (45점)
이 서브태스크는 추가 제한 조건이 없다.
예제 입력 1
3 1 4 1 5 9 2
예제 출력 1
2
예제 입력 2
4 0 1 0 2 0 3 0 4
예제 출력 2
1
출처
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호