경이로운 그리디 알고리즘2 -인접한 원소간 차이로 그룹을 나누는 방법-

1. 문제1

 

13164번: 행복 유치원 (acmicpc.net)

13164번: 행복 유치원

 

2. 풀이

 

크기가 n인 배열을, 인접한 원소끼리 그룹으로 나누고자 하는데,

 

그룹간 최댓값과 최솟값의 차이의 합이 최소가 되도록 k개의 그룹으로 나누고자 할때,

 

그 차이의 합의 최솟값을 구한다면?

 

모르는데 생각해낸다면 정말 재능있는거고.. 테크닉을 알아도 감탄밖에 안나온다

 

--------------------------------------------------------------------------------------------------------------------------------

 

최댓값과 최솟값의 차이를 구해야할테니, 배열을 정렬하는건 기본적으로 할테고

 

오름차순으로 정렬된 배열 $$x_{1}, x_{2}, ... x_{n-1}, x_{n}$$ 에 대해 먼저 생각해보자.

 

그렇다면 현재 초기 상태에서 드는 비용은 $$x_{n} - x_{1}$$

 

만약에 어떤 $x_{i}$를 기준으로 두 그룹으로 분리한다고 생각해보자.

 

$$x_{1}, x_{2}, x_{3}, ... x_{i}$$ 와 $$x_{i+1}, x_{i+2}, ... x_{n}$$

 

두 그룹의 비용은 각각 $x_{i} - x_{1}$이고 $x_{n} - x_{i+1}$이다.

 

그러므로 비용의 합은 $$(x_{n} - x_{1}) - (x_{i+1} - x_{i})$$

 

이것이 무엇을 뜻할까?

 

원래 상태에서 $x_{i}$를 기준으로 두 그룹으로 분리한다고 하면, 원래 비용에서 $x_{i+1} - x_{i}$만큼 감소한다는 것을 알 수 있다.

 

그렇다면 그룹간 비용의 합이 최소가 되도록 k개의 그룹으로 분리해야한다면 어떻게 해야할까?

 

배열에서 1개의 원소를 선택해서 분리하면 2개의 그룹으로 분리되고,

 

2개의 원소를 선택해서 분리하면 3개의 그룹으로 분리되고,.

 

...

 

k-1개의 원소를 선택해서 분리하면 k개의 그룹으로 분리된다.

 

그래서 원래 배열을 오름차순으로 정렬한 다음,

 

인접한 원소간 차이 $x_{i+1} - x_{i}$를 모두 구한 다음에, 오름차순으로 정렬하고,

 

$x_{i+1} - x_{i}$가 가장 큰 값부터 k-1개의 값을 원래 비용 $x_{n} - x_{1}$에서 빼나가면, 

 

그것이 k개의 그룹간 비용의 합의 최솟값이 될 것이다.

 

------------------------------------------------------------------------------------------------------------------------------------------

 

알고리즘 풀면서 2번째로 지렸다...

 

from sys import stdin

n,k = map(int,stdin.readline().split())

#주어진 배열을 먼저 정렬하고,
height = list(map(int,stdin.readline().split()))

height.sort()

#초기 상태의 비용을 구한다
max_cost = height[-1] - height[0]

#인접한 원소간 차이를 구하고 정렬해서
minus = []

for i in range(n-1):
    
    minus.append(height[i+1] - height[i])

minus.sort()

#인접한 원소간 차이가 가장 큰값부터 k-1개를 차례대로 원래 비용에서 빼면
#그것이 k개의 그룹간 비용합의 최솟값
while k > 1:

    max_cost -= minus.pop()
    k -= 1

print(max_cost)

 

3. 문제2

 

2212번: 센서 (acmicpc.net)

2212번: 센서

 

4. 풀이

 

잘 읽어보면 위 문제랑 정확히? 똑같은 문제다

 

"최대" k개의 집중국을 세워서 각 집중국의 수신 가능 영역의 길이 합을 최소화 시키는게 목표

 

여기서 배열의 n개의 원소가 적어도 하나의 집중국과는 통신이 가능해야한다.

 

------------------------------------------------------------------------------------------------

 

"최대"라는 말로 사람을 헷갈리게 한다

 

k개를 다 안써도 되나?

 

1) 근데 수신 가능 영역의 길이 합을 최소로 만들고 싶으면, 당연히 k개의 집중국을 전부 사용해야 최소로 만들 수 있을것

 

------------------------------------------------------------

 

다음에 "수신 가능 영역의 길이가 0 이상이라고" 조건을 명시했다는 것은, 배열의 원소에 집중국을 세워야 무조건 이득이다

 

배열의 원소가 아닌 다른곳에 집중국을 세우면 수신 영역을 무조건 1이상은 사용해야하니, 길이에서 손해본다는거지

 

근데 지금 생각해보면 꼭 그런것은 아닌듯...?

 

-----------------------------------------------------------

 

배열의 n개의 원소가 적어도 하나의 집중국과 통신이 가능해야한다는 것은,

 

하나의 집중국이 중심이 되어 일부 원소들이 하나의 그룹을 이루라는 말이 될 것이다

 

----------------------------------------------------------------

 

수신 가능 영역의 길이는 어떻게 구해야할까?

 

각 그룹에서 수신 가능 영역의 길이가 최소가 될려면 어떻게 해야할까?

 

최댓값과 최솟값의 차이의 절반이 각 그룹의 수신 가능 영역 길이의 최솟값일 것이다.

 

 

왜냐하면, 중앙에서 양 옆으로 조금만 움직여도 수신 가능 영역의 길이가 커지니까

 

아무튼, 각 그룹에서 수신 가능 영역의 길이는 $\frac{x_{n} - x_{1}}{2}$일 것이다.

 

결국에 위 문제와 동일하다. 

 

단순히 $\frac{1}{2}$로 나눴을뿐

 

아니 근데 이렇게 하면 1번 예제가 답이 5가 아니고 4잖아...

 

"수신 가능 영역의 길이"라는게 한쪽 길이인 4를 의미하는게 아니고, 양쪽 길이의 합인 8을 의미하는듯?

 

그래서 "수신 가능 영역의 길이"는 각 그룹에서 "최댓값과 최솟값의 차이"를 말하겠네

 

따라서 행복 유치원 문제와 완전히 동일한 문제다..

 

센서 좌표를 받아서, 오름차순으로 정렬하고

 

초기 상태 sensor[-1] - sensor[0]을 비용으로 둔 다음에, 인접한 원소간의 차이 sensor[i+1] - sensor[i]를 구해

 

이들을 정렬하고, 가장 큰 값부터 k - 1개를 초기 상태 비용에서 빼나가면, 그것이 수신 가능 영역 길이의 합의 최소이다.

 

from sys import stdin

n = int(stdin.readline())

k = int(stdin.readline())

sensor = list(map(int,stdin.readline().split()))

#n < k이면, k개 집중국을 모두 n개의 좌표 위에 세우면 되니 길이 합이 0
if n < k:
    
    print(0)

# n >= k
else:
    
    #센서 좌표를 오름차순 정렬
    sensor.sort()
    
    #초기 비용을 최대 - 최소로 초기화
    max_cost = sensor[-1] - sensor[0]
    
    #인접한 원소간 차이를 구해서 정렬하고
    minus = []

    for i in range(n-1):

        minus.append(sensor[i+1]-sensor[i])

    minus.sort()
    
    #인접한 원소간 차이를 큰 값부터 k - 1개 선택해서 초기 비용에서 빼나가면
    #그것이 k개를 설치했을때 수신 가능 영역 길이의 합의 최소이다.
    while k > 1:

        max_cost -= minus.pop()
        k -= 1

    print(max_cost)

 

굳이 한가지 함정이라면, n < k일 수도 있다는 점?

 

n < k라면, k개의 집중국을 모든 n개의 좌표 위에 세우면 되니까,

 

각 집중국의 수신 가능 영역의 길이 합은 해당 좌표 그 자체만을 수신하면 되니 0이 된다