[백준] 13164 : 행복 유치원 (파이썬)

Algorithm/Greedy

[백준] 13164 : 행복 유치원 (파이썬)

_은선_ 2024. 8. 15. 16:04

SMALL

그리디 문제

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

초기 접근 방식

1. 이진탐색

이 문제를 처음에 그리디로 접근하고자 하였으나, 생각보다 잘 풀리지 않아 그 다음 방식으로 이진 탐색을 떠올렸다.

백준에 있는 공유기 설치 문제와 유사하다고 생각하여 이 문제 또한 이진탐색으로 접근하여 문제를 풀어보았다.

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

2. 잘못된 이유

이진 탐색에서 mid의 의미가 명확하지 않다.
- 공유기 설치 문제 : mid = 공유기 사이의 최대 간격 -> 이를 바로 답에 활용할 수 있었음.
- 행복 유치원 문제 : mid = 조를 S개 만큼 나누면서, 각 조의 첫번째 원생 사이의 간격이 최소가 되도록 하는 수 -> 문제에서 요구하는 바와 일치하지 않음.
이 문제에선 각 조의 첫번째 원생 사이의 간격이 중요한 것이 아니다.
- 각 조(1조,2조,3조,...)의 첫번째 원생 사이의 간격이 아무리 커도 상관없다.
- 각 조 내에서 첫번째 원생과 마지막 원생 사이의 간격(키 차이)이 최소가 되도록 K개의 조로 나누는 것이 목적이다.

3. 이진탐색 코드 (실패)

import sys 
n, s = map(int, sys.stdin.readline().split())
arr = [0]
arr += list(map(int, sys.stdin.readline().split()))
arr.sort()

def binary_search():
    left = 1
    right = max(arr)
    ans = 0

    while left <= right:
        mid = (left + right) // 2

        cnt = 0
        last = arr[1]
        for i in range(1, n + 1):
            if arr[i] <= last + mid:
                cnt += 1
        
        if cnt >= s:
            right = mid - 1
            ans = mid
        else:
            left = mid + 1
    return ans
dist = binary_search()
arr.append(0)

last = 1
result = 0
for i in range(1, n + 2):
    if arr[i] >= arr[last] + dist:
        result += arr[i - 1] - arr[last]
        last = i 
print(result)

접근 방식

이 문제는 이진 탐색을 사용하여 최적의 비용을 찾는 문제보다는, 차이 배열을 정렬한 후 가장 큰 차이들을 잘라내는 그리디한 접근이 더 적합하다.

그리디

k개의 조로 나눌때 나누는 칸이 k-1개가 필요하다.

여기서 막대기라고 표현한다면 막대기를 인접한 원생과의 차이가 가장 크게 나는 곳에 두어야 한다.

키 차이가 가장 크게 나는 곳에 막대기를 두게 되면, 해당 키차이(비용)은 제외되기 때문이다.

N명의 원생
K개의 조 : N명의 원생들을 나눠야 하는 조의 개수로, 원생-원생 간의 키 차이를 하나 뛰어넘게 해주는 역할을 한다.
- 만약, 조가 2개라면 원생-원생 간의 키 차이를 하나 뛰어넘을 수 있다.
- 만약, 조가 3개라면 원생-원생 간의 키 차이를 2개 뛰어넘을 수 있다.

예시:

5 3
1 3 5 6 10
2 2 1 4 -> 키차이

키차이가 2,4인 곳에 막대기를 둔다면
1 3 | 5 6 | 10 -> 비용 : 2 + 1 = 3 (최소 비용)

1. 인접한 원생들 사이의 키 차이를 계산하여 차이 배열을 만든다.
2. 차이 배열을 정렬하여 가장 큰 차이들을 선택한다.
3. 가장 큰 K-1개의 차이를 잘라내고, 나머지 차이들의 합을 최소 비용으로 반환한다.

💡 풀이코드 (성공)

import sys 
n, s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

def sol(n, s, arr):
    minusArr = []

    for i in range(1, n):
        minusArr.append((arr[i] - arr[i - 1]))
    minusArr.sort()
    print(sum(minusArr[:n - s]))

sol(n, s, arr)