하늘에 닿기
시간 제한1초메모리 제한1024 MB
고도 0에서 시작해, balloon i는 고도 L_i 이하에서만 부풀릴 수 있고 집을 D_i만큼 들어올린 뒤 터진다. 터뜨릴 수 있는 풍선 개수의 최댓값을 구한다.
문제
사진은 풍선으로 하늘에 띄운 집이다. 2018 KAIST RUN Spring Contest 포스터에도 쓰였다.
서기 2117년, 유재민 교수가 TSP (Traveling Salesperson Problem)의 선형 시간 알고리즘을 만들었다. 얼마 지나지 않아 모든 컴퓨터 시스템이 무너졌고, 세상은 핵무기로 황폐해졌다. 컴퓨터 과학의 최고 전문가이던 당신도 할 일을 잃었고, 절망 속에서 인생의 의미를 잃어버린 지 오래다. 그동안 당신의 심장을 뛰게 하던 것들은 모두 어디로 갔을까? 끝없이 자신에게 물은 끝에 내린 결론은 이렇다.
"ICPC를 처음 시작한 그때 그 카이스트에 가면, 내 인생의 의미를 찾을 수 있지 않을까?"
도로망도 철도도 황폐해진 지 오래다. 그렇지만 열렬한 ICPC 참가자였던 당신은 100년 전 대전 대회에서 받은 풍선을 여전히 가지고 있다. 그 풍선으로 집을 띄울 수만 있다면.
지금 당신에게는 풍선이 개 있고, 당신은 풍선을 하나씩 지붕에 매달아 집을 하늘로 띄우려 한다. 번 풍선에는 고도 제한 와 용량 가 있다. 기압의 영향으로 고도 이하에서만 이 풍선을 불 수 있고, 이 풍선은 집의 고도를 만큼 올린 뒤 터진다.
당신의 여정은 고도 에서 출발한다. 부풀어 있는 풍선이 2개 이상이면 집이 너무 빠르게 올라가므로, 당신은 풍선 하나를 불어 지붕에 매단 뒤 그 풍선이 터질 때까지 고도를 올리고, 터진 뒤에 또 하나를 불어 터질 때까지 고도를 올리는 과정을 반복해서 집을 띄울 예정이다. 편의상 풍선이 터진 뒤 다음 풍선을 매다는 동안에는 고도가 변하지 않는다고 가정한다. 즉 고도를 바꾸는 것은 풍선뿐이다.
최종 고도는 어디든 상관없다. 다만 풍선 하나는 터지기 전까지 일정한 거리를 움직여 주니, 최대한 많은 풍선을 터뜨리는 편이 좋다. 터뜨릴 수 있는 풍선의 최대 개수를 구하여라.
입력
첫 번째 줄에 풍선의 개수 이 주어진다.
다음 개의 줄 중 번째 줄에는 번 풍선의 고도 제한 와 용량 를 뜻하는 정수 2개가 공백으로 구분되어 주어진다.
출력
터뜨릴 수 있는 풍선의 최대 개수를 한 줄에 출력한다.