BOJ #2212

---

LEVEL :

Gold5

---

문제 요약 :

각 k개의 집중국 각각이 최소한의 영역으로 모든 센서를 감싸는 경우의 각 집중국의 영역의 총합

---

해결 방안 :

오랜만에 공부하는 알고리즘 공부라 그런지 문제를 너무 직관적이게만 보는 경향이 있는 것 같다.. 자만하지말고 적으면서 공부해야지...
먼저 이번문제에 대한 접근으로 dfs 방법으로 접근 했다. 각 센서를 오름차순으로 정렬한 뒤, k개의 집중국이 모든 영역을 차지할 수 있도록 dfs를 통해 모든 경우를 확인 하였더니 ,,, 시간 복잡도는 O(N^2) 풀면서 알 수 있었다 이건 무조건 시간 초과임을 ㅋㅋ 결국 채점결과 9%를 넘어가니 내가 예상한 결과가 나오는 것을 알수있었다. 그래서 새로운 마음으로 해당 문제의 정확한 풀이법 고안을 위해 그림을 그려가며 문제를 다시 이해해보았다..
그러고 10분여간 고민한 뒤 번뜩한 생각, 각 센서간의 차이를 구한뒤 내림차순으로 정렬하여 ,k-1번의 영역을 뛰어넘을 수 있다는 것을 알수있었다.
이렇게 하면 총 O(NlogN) 즉, 오름차순, 내림차순 정렬시 사용되는 시간복잡도만 고려하면 된다. 결과는 통과!
흠 뭐랄까 이번 문제는 쉬운문제였음에도 문제의 이해와, 해결과정에서 꽤 힘들었던 문제였던 것 같다.

Solution1. -> FAIL

import sys
import copy
input = sys.stdin.readline

def dfs(sensors,left,area_sum,start) :
    global min_area
    left_sensors = copy.deepcopy(sensors)
    if area_sum >= min_area :
        return
    if left == 1 or (len(left_sensors) == 1 and left > 1):
        area_sum += (left_sensors[len(left_sensors)-1]-left_sensors[0])
        min_area = min(area_sum,min_area)
        return
    while left_sensors :
        val = (left_sensors[0]-start)
        area_sum += val
        popped = left_sensors.pop(0)
        dfs(left_sensors,left-1,area_sum,popped)
        area_sum -= val

if __name__ == "__main__" :
    sys.setrecursionlimit(20000)
    n = int(input().strip())
    k = int(input().strip())
    arr = sorted(list(set(map(int,input().strip().split())))) 
    min_area = arr[len(arr)-1] - arr[0]   
    dfs(arr,k,0,arr[0])
    print(min_area)

Solution2. -> SUCCESS

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    n = int(input().strip())
    k = int(input().strip())
    arr = sorted(list(map(int,input().strip().split()))) 
    dist = []
    for i in range(n-1) :
        diff = arr[i+1] - arr[i]
        dist.append(diff)
    dist.sort(reverse=True)
    print(sum(dist[k-1:]))

---

시간 복잡도 :

• Tim정렬 : NlogN