알고스팟 ANNIETIBBER

애니 티버가 서로 봤을 때 좌우 관계가 반대인 쌍의 수를 세는 문제이다.

각도로 정렬하면 답이 되는 경우는, 정렬된 배열 상에서 애니가 기준으로 보는 별의 왼쪽에 있는 별이 티버 배열에선 오른쪽에 있는 경우이다. 이는 inversion의 수와 같다.

머지소트를 짜거나, 구간합을 계산할 수 있는 자료구조를 쓰면 된다.

댓글

댓글 쓰기