220917 문제 풀이 기록

P4 | 5922 - Above the Median

풀이 시간: 약 30분

시도 횟수: 1회

체감 난이도: P4

풀이 쓸 의향: 下

풀이

X 이상을 1, X 미만을 -1로 두고 부분합의 개수 control하기.

무조건 부분합은 -n~n까지이므로, 일단 초기에는 부분합이 0 이상인 개수 counting한 뒤 시작점이 1번인것부터 하나씩 날리면서 개수 counting 한 합 구하기.

여담: 너무 안보이길래 태그 슬쩍 보고 풀었다... "아니 대체 h가 10억 제한인데 중간값을 어떻게 구해" 부터 시작하는 뇌절을 빠르게 끊어주는 핵심 아이디어를 토대로 그나마 수월하게 푼듯하다. 역시 중앙값을 구하기가 그렇게 쉬울리가 없지..