SWEA 4111. 무선 단속 카메라 (Python)

한마디

파이썬의 Set 넘모 강력하다 ! sort도 넘모 좋아! 너희 없으면 나 코딩 못해

 

 

 

* 위 문제의 저작권은 SW Expert Academy 에 있습니다. 

문제 링크는 여기

SW Expert Academy

무선 단속 카메라의 정보를 수신할 수 있는 수신기를 가장 효율적으로 설치했을 때에 수신 거리를 구하는 문제!

알고리즘 되게 기발하다고 생각했는데 생각해보니까 이 로직이 아니면 풀 수 있는 방법이 없긴 한 것 같다ㅎ

 

Idea

• 어떤 두 카메라가 같은 수신기를 공유한다고 했을 때 수신거리의 합은 수신기가 두 카메라 사이 어디에 있든지간에 두 카메라의 거리의 차이다.
• 카메라는 같은 위치에 있을 수도 있으므로, 처음에 set로 한번 받아줬다가 list로 바꿈으로써 중복값을 없애준다.
• 수신거리의 합이 적기 위해서는 두 카메라 사이의 거리의 차가 큰 곳의 두 카메라를 각각 다른 수신기로 끊어주는 작업이 필요하다. 

 

Code

#4111. 무선 단속 카메라
#code written by pg-wonie

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    K = int(input())
    dist = 0
    cameras = sorted(list(set(map(int, input().split())))) #중복값을 없애주고 거리 순으로 정렬
    if K >= len(cameras): #수신기가 카메라보다 많으면 수신거리의 합은 0이 된다. 
        print('#{} {}'.format(test_case, dist))
        continue
    diff = []
    for i in range(len(cameras)-1):
        diff.append(cameras[i+1] - cameras[i]) #두 카메라 사이의 거리의 차를 넣어준다.
    diff.sort() #정렬
    print('#{} {}'.format(test_case, sum(diff[:len(diff)-K+1]))) 
    #수신기-1 만큼 큰 차를 없애준 것들의 합을 출력한다.

dfs나 순열이 필요할 것이라고 생각했는데, 첫 로직을 세웠더니 생각보다 빠르고 짧은 코드가 나올 수 있었다!