[백준 - 31589] 포도주 시음 🍷

❓ Problem

🤔 How

어떤경우에 포도주로 최고의 만족감을 얻을수 있을까 Greedy 하게 접근해보자. 😀

구현 로직

1. 우선 탐욕법으로 접근하기위해 포도주가 순서대로 정렬되어있어야한다.
2. 포도주 에서 마실수있는 최고의 포도주를 마신다.
3. 남은 포도주 에서 최저의 만족감을 주는 포도주를 마신다. (이미 최고의 포도주를 마신 뒤이므로 효용은 0이다.)
4. 2->3 을 반복한다.

🍷 최적해를 찾아 탐욕적으로 접근하기 포도주에서는 어떻게 작동할까

1. 우선 포도주에서 마실수있는 최고 효용을 K 라고 했을때 첫잔에서 얻을수있는 최고만족감은 언제나 K이다.
2. 그후 남은 포도주에서 마실수있는 최저의 효용을 얻는다. 이때 얻을수있는 만족 효용은 0이다.
3. 남은 포도주중에서 최고 효용의 포도주를 마신다. 이때 얻을 수 있는 효용은 현재마신 포도주 - 이전에 마신 포도주이다.
   이를 반복하면서 탐욕적으로 접근할 수 있다.

❗ Solve

# 포도주 시음
import sys

input = sys.stdin.readline


def solution():
    N, K = map(int, input().split())  # 갯수와 ,주량
    wines = [0] + list(map(int, input().split()))
    wines.sort()
    prev = 0
    end = len(wines) - 1
    cnt = 0
    ans = 0
    while cnt < K:
        if cnt % 2:
            prev += 1
            cnt += 1
        else:
            ans += wines[end] - wines[prev]
            end -= 1
            cnt += 1
    print(ans)

    pass


if __name__ == "__main__":  # 실행되는 부분
    solution()
    pass