[Python/BOJ] 백준2212 센서_그리디

 

 

https://www.acmicpc.net/problem/2212

2212번: 센서

 

 

 

5번을 읽었는데 문제가 잘 이해가 안되서 답을 찾아봤다.😂

 

그냥 쉽게 말하면 n개의 센서를 k개의 구간으로 나누기 더만!!

내가 독해력이 떨어지나....ㅋㅋㅋ

< 참고 블로그에 자세히 설명이 있으니 참고 하세용>

 

 

 

 

정렬을 이용하여 그리디 방식으로  풀이하였다. 

 

 

- 만약 집중국의 개수가 센서보다 크거나 같다면 0이다. 

 

1) 센서들을 순서대로 만든다.(오름차순 정렬)

2) 센서들간의 거리 계산 

3) 거리를 내림차순으로 정렬한다.

4) k개의 구간으로 나누려면 k-1번 잘라야하므로  이것은 k-1번의 거리를 제거해도 된다는 것이다. 

5) k-1번 거리를 큰것부터 제거한다.

6) 남은 거리의 총 합을 구해 출력한다. 

 

 

 

 

코드 : 

if __name__=="__main__" :
    n = int(input())
    k = int(input())
    sensor = list(map(int,input().split()))
    
    # 집중국이 더 많을 경우 
    if k >=n : 
        print(0)
        exit(0)
    else :
    	# 오름차순 정렬 
        sensor.sort()
        cha = []
        # 간격을 구한다. 
        for i in range(1,len(sensor)) :
            cha.append(sensor[i]-sensor[i-1])
        # 내림차순 정렬 
        cha.sort(reverse=True)
        # k-1개 제거 
        for i in range(k-1) :
            cha.pop(0)
        print(sum(cha))

 

 

 

 

 

 

 

 

 

 

 

 

참고 블로그 : 

https://journeytosth.tistory.com/16

[알고리즘] 백준 2212번 : 센서