algospot 너드인가, 너드가 아닌가? 2 (문제 ID: NERD2) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/NERD2

algospot.com :: NERD2

p와 q가 다음과 같이 정의된다.

p: 알고스팟 온라인 채점 시스템에서 푼 문제의 수

q: 밤 새면서 지금까지 끓여먹은 라면 그릇 수

대회에 참가하려는 신청자 a의 문제 수 pa와 그릇 수 qa를 다른 참가 신청자 b의 문제 수 pb와 그릇 수 qb에 비교한다.

이때, pa < pb && qa < qb 이면 신청자 a는 대회에 참가할 수 없다.

한 사람의 참가 가능 여부는 다른 사람들의 문제와 라면 그릇 수에 의해 결정 되기 때문에,

대회에 참가할 수 있는 사람의 수는 새로운 사람이 참가 신청을 할 때마다 계속 바뀐다.

 

신청자들 각각의 p와 q를 x, y로 바꿔서 이차원 평면의 점들로 생각해보자.

대회에 참가하기 위해서는 기존의 점들보다 x값이 크거나 y값이 크거나 둘중 하나는 해야된다.

이는 곧 신청자의 (p,q)에서 p에 바로 오른쪽 점의 y좌표가 q보다 작아야 한다.

위 기준에 맞아서 새 신청자를 참가시킬시에는 새점 (p,q)에서 p에 왼쪽에 있는점의 y좌표가 q보다 작다면 더 이상 대회에 참가할 수 없다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/22.%20BinarySearchTree/NERD2.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2