python 2212번 센서 (백준)

t = int(input())
n = int(input())
a = list(map(int,input().split()))
a.sort()
a = [abs(b-a) for a,b in zip(a,a[1:])]
a.sort()
print(sum(a[0:t-n]))

 

풀이 : 정렬

1. 집의 좌표를 오름차순으로 정렬합니다 (내림차순도 상관없습니다)

2. 각 집끼리의 차이를 (음의 정수가 아닌 정수로) 계산합니다. 만약 같은 좌표라면 결과는 0입니다

3. 2에서 구한 차이들을 또 정렬합니다.

4. 가장 큰 차이부터 (집중국의 개수 -1) 만큼 제거합니다.

5. 4에서 남아있는 차이들의 합이 답입니다.

 

4에서 제거한다는 것은 위의 그림을 보면 새로운 집중국을 설치하는것으로 여길수 있습니다

0 1 1 2 2 3 에서 (집중국 1개)

0 1 1 2 2 |  0   (집중국 2개)

 

1 1 1 2 2 2 2 3 3 (집중국 1개)

1 1 1 2 2 | 0 | 0 | 0 | 0 (집중국 5개)

 

코드 분석

첫번째 줄 : t을 입력받습니다.

두번째 줄 : n을 입력받습니다.

세번째 줄 : 입력받은 문자열을 공백을 기준으로 나눈 다음 정수형으로 바꾼것을 a라는 list에 집어 넣습니다.

네번째 줄 : a를 오름차순 정렬 합니다.

다섯번째 줄 : zip(a,a[1:]) 리스트 a의 0번요소부터와 리스트 a의 1번요소부터를 1개씩 짝 짓습니다. (짝을 짓지 못하는 것은 제외됩니다)  그리고 나서 이것을 각각 a,b 로 여기며 반복하면서, abs(b-a)의 값을 새로운 리스트의 구성요소로 집어 넣습니다. 이 새로운 리스트를 a에 대입합니다.

여섯번째 줄 :  a를 오름차순으로 정렬합니다.

일곱번째 줄 : 가장 큰 차이의 값부터 (k-1)개 제거한 값들의 합(sum)을 출력하면 됩니다.

ex) 집 6개, 집중국 2개

-집이 6개이니 만들어지는 차이는 5개 (0번부터 4번)
[0:4] 0이상 4미만이므로 4번 1개(집중국개수 2개  - 1 = 1) 만을 제거한 것으로 볼 수 있다.