백준23322(초콜릿 뺏어 먹기)

초콜릿 뺏어 먹기

 

문제

연두는 $N$개의 통에 초콜릿을 담아서, 초콜릿의 개수가 오름차순이 되도록 일렬로 배열해 놓는다. 즉, ($1$번째 통의 초콜릿의 개수) $\le$ ($2$번째 통의 초콜릿의 개수) $\le \dots \le$ ($N$번째 통의 초콜릿의 개수)이다. 

효원이는 매일 조금씩 연두의 초콜릿을 몰래 뺏어 먹을 계획을 세우는 중이다. 연두는 매우 눈치가 없기 때문에, 하루에 한 번 다음의 전략을 사용해서 초콜릿을 먹는다면 절대 눈치채지 못할 것이다.

1.  $K<i$인 $i$를 골라, $i-K$번째 통에 있는 초콜릿의 개수와 똑같아질 때까지 $i$번째 통에서 초콜릿을 꺼내 먹는다.
2. 그 후 통을 재정렬한다. 즉, 초콜릿의 개수가 오름차순이 되도록 통을 재배치 한다.

효원이는 연두가 눈치채지 못하는 선에서 최대한 많이, 그리고 최대한 빨리 초콜릿을 먹어 치우고 싶다. 과연 몇 개나 먹을 수 있을까?

 

입력

첫 번째 줄에 통의 개수 $N$과 $K$가 주어진다. ($1 \le K < N \le 2\,000$)

두 번째 줄에 초기에 $i$번째 통에 들어있는 초콜릿의 개수 $a_1, a_2, \dots, a_N$이 주어진다. ($1 \le a_1 \le a_2 \le \dots \le a_N \le 2\,000$)

 

출력

연두에게 들키지 않으면서 먹을 수 있는 초콜릿의 최대 개수와, 그 개수의 초콜릿을 먹기 위해 필요한 최소 날짜를 출력한다.

---

계속 순서가 바뀌고 처음 비교는 처음과 K + 1번째 상자를 비교하고 이후 뒤로 가게 되는데 그렇게 되면 결국 모든 상자에 초콜렛의 수가 처음 상자의 초콜렛 수와 같아 질 수 밖에 없다. 이를 이용해서 첫 번째 상자와 다른 모든 상자를 비교하는 방식으로 하였다.

'''
초콜릿 뺏어 먹기

'''
import sys
input = sys.stdin.readline

N, K = map(int,input().split())
chocolates = list(map(int,input().split()))

# 날짜와 갯수
days = 0
cnt = 0
# 가장 작은 수의 초콜렛(목표 초콜렛 수)
fix_choco = chocolates[0]

# 결국 모든 상자와 비교하게 되기 때문에 
# 처음 상자를 제외하고 비교
for i in range(1,N):
    # 다르다면 그만큼 초콜렛을 빼게 되고 
    # 하루가 흐른다
    if chocolates[i] != fix_choco:
        cnt += (chocolates[i] - fix_choco)
        days += 1

print(cnt, days)