moner_ari   1년 전

[문제]

소들이 열심히 돌아다니며 운동하려 나오고 있습니다! 무한히 긴 트랙 하나에 N마리의 소들이 조깅을 하고 있습니다. (1 <= N <= 100,000) 모든 소들은 각각 트랙의 서로 다른 위치에서 출발하며, 몇몇 소들은 서로 다른 속력으로 조깅합니다.

트랙이 하나뿐이므로, 소들은 서로 추월할 수 없습니다. 더 빠른 소가 다른 소를 따라잡을 때, 더 느린 소에 부딪히지 않기 위해 더 빠른 소는 속도를 늦춰야 하며, 그 결과 두 소는 하나의 그룹을 이뤄 달리게 됩니다.

결국에는 어떤 소들도 서로 부딪히지 않을 것입니다. 이때 농부 존은 소들이 얼마나 많은 그룹을 이뤄서 달리게 될지 궁금해합니다. 그를 도와 얼마나 많은 그룹이 있을지 계산해 주세요.

--------

[입력]

입력의 첫 줄에는 정수 N이 입력됩니다.

다음 N개 줄에는 한 마리의 소의 초기 위치와 속력이 입력됩니다. 위치는 음수가 아닌 정수이고 속력은 자연수이며, 두 수의 최댓값은 모두 10억(1,000,000,000)입니다. 모든 소는 서로 다른 위치에서 출발하며, 입력은 위치의 오름차순으로 주어집니다.

--------

[출력]

마지막에 남게 되는 그룹의 개수를 하나의 정수로 출력합니다.

댓글을 작성하려면 로그인해야 합니다.