purple_beluga   1년 전

저는 N의 범위가 적어서 브루트포스 알고리즘으로 이중 for문을 써서 단순 비교 방식을 사용했습니다. 

근데 N의 범위가 무수히 큰 수일 때는 이중 for문으로는 시간복잡도가 N^2이므로 너무 오래 걸린다고 생각합니다. 

따라서 제가 지금까지 알고있는 지식으로는 heap, quick, merge 정렬의 사용을 떠올렸습니다. 

하지만 도저히 구성방향이 생각나지 않습니다. 따라서 약간의 방향성을 지시해주셨으면 감사하겠습니다. 

// 무조건 정렬을 사용하여 푸는 방식을 고집하는 것은 아닙니다. 제가 생각한 방향성과 아예 달라도 괜찮습니다.

jiminp   1년 전

여러 가지 방법이 있는데, 제일 쉽게 떠오르는 방법은 세그먼트 트리를 하나 만들고, 몸무게가 줄어드는 순서로 정렬한 뒤, 신장을 좌표압축한 인덱스에 1씩 증가시키는 방법입니다. 세그먼트 트리 대신 적당한 balanced tree (레드블랙 등...)를 활용해도 됩니다. 이렇게 하면 O(n log n)이겠네요.

2차원 펜윅 트리를 활용하면 조금 더 직관적이지만 비효율적인 O(n (log n)^2) 풀이도 존재합니다.

참고로 상위 버전으로 2336번 문제가 있습니다.

https://www.acmicpc.net/proble...

purple_beluga   1년 전

큰 틀이 잡힌 듯 합니다. 답변에 감사합니다. ^^

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