[백준 2024/02/23] 2212번 센서

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

2212번: 센서

 

1. 접근 방법

이 문제는 문제 자체는 어렵지 않았다고 생각한다.

 

하지만, 문제를 이해하는데 시간을 많이 쓴 것 같다. 문제 해석에 모호한 부분이 있었다고 생각한다. 조금 개인적인 생각이다.

집중국이 어떤 방식으로 수신 가능 영역을 조절하는지, 집중국을 어떤 방식으로 거리를 나타내는지, 그런 설명이 필요하지 않았나...

처음에 나는 집중국에서 radius 처럼, 집중국을 중심으로 r 거리만큼, sensor를 조절한다고 생각했다.

 

k개의 집중국을 가지는 것은 k개의 묶음을 가지는 것과 같다.

k개의 묶음을 가지기 위해서는 k-1 번 자르면 된다.

그때, 자르는 기준은 가장 긴 거리 차이를 가지는 곳이 될 것이다.

 

왜냐하면 그곳을 잘라야지, 수신 가능 영역 길이가 작아질 것이기 때문이다.

 

이 예제를 가지고 더 알아볼 것이다.

 

거리에 따라서 값을 넣어주고 오름차순 정렬을 해주었다. 

해당 문제의 경우, 주어진 sensor의 경우, set을 통해 중복을 없애주고, .sort를 통해 오름차순 정리를 해주었다.

이후 sensor들 간의 거리 차를 구한 후, 가장 큰 값이 먼저오도록 내림차순 정리를 해주었다.

 

[1, 3, 6, 7, 9] # sensor의 위치
[3, 2, 2, 1] # 거리 차

 

이런 식으로 작성해 주었다.

def min_distance_sum(dff, k):
    for i in range(k-1):
        if dff:
            max_d = dff.pop(0)

    return sum(dff)

이후 k-1번 만큼 pop(0)를 해주었다. -> k-1 번 잘라, k개의 묶음을 가지기 위함이다.

 

2. 코드

def input_sensors():
    sensor_len = int(input())
    k = int(input())
    sensors = set(map(int, input().split()))
    sensor = list(sensors)
    sensor.sort()
    return k, sensor


def diff_sensor(sensor):
    dff = []

    for i in range(len(sensor) - 1):
        dff.append(sensor[i + 1] - sensor[i])

    dff.sort(reverse=True)

    return dff


def min_distance_sum(dff, k):
    for i in range(k-1):
        if dff:
            max_d = dff.pop(0)

    return sum(dff)


def main():
    k, sensor = input_sensors()
    diff = diff_sensor(sensor)
    print(min_distance_sum(diff, k))


if __name__ == "__main__":
    main()