반응형 2399 썸네일형 리스트형 [BOJ 2399] 거리의 차이 2399번 (거리의 차이) 이 문제는 단순히 이중 반복문을 이용하여 (x[0] ,x[0]~x[n]) , (x[1], x[0]~x[n]), ... (x[n], x[0]~x[n]) 이렇게 총 n^2개의 모든 쌍을 구하는 방식으로 구할 수 있다. 하지만 이 방식은 시간복잡도가 O(n^2)이기 때문에 n이 커지면 시간이 오래 걸리게 되고, 또 이 문제의 분류가 "정렬" 이기 때문에 정렬을 이용하여 문제를 풀어보았다. 정렬을 이용한 풀이에는 아주 유용한 "수학적인 아이디어"가 이용된다. 1. 우선 정렬을 통해서 n개의 점을 좌표가 오름차순이 되도록 정렬을 한다. 2. 특정한 x[i]를 생각해보면, 모든 n^2개의 쌍 중에서, x[i]는 총 2n번 등장하게 된다. (x[1] ~ x[n] , x[i]) : n개 / .. 이전 1 다음
