[백준 23322] 초콜릿 뺏어 먹기(질문)

[BanApp]

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

import sys

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

key = min(arr)
a = 0
day = 0

for i in range(n):
    if arr[i] > key:
        day = day + 1
    a = a + (arr[i] - key)

print(a,day)

그리디 알고리즘으로 풀었는데 보니깐 조건에서 i-k 가 기준이기 때문에 결국엔 나중에 가장 작은 값인 arr[0]를 기준으로 맞춰진다고
생각해서 풀었습니다. 문제 예제의 예시처럼 k보다 큰 i번을 먼저 뽑고 순서를 바꾸는 정공법 방식(?)으로 풀지 않았는데
제가 생각한게 맞는건지 아니면 테스트 케이스가 부족해서 정답처리가 된건지 궁금합니다. 의견 부탁드립니다.^ㅇ^/

[ghdcksgml1]

이 그리디 알고리즘이 가능한 이유는 첫째는 문제에서 처음 주어진 초콜릿 통에 담긴 초콜릿의 개수가 오름차순으로 주어졌고, 두번째는 최대한 많이 빠른시간내에 먹으려하기 때문에 가능한 것 같습니다.

두번째 조건을 만족시키기 위해서는 가장 작은 숫자인 첫번째 인덱스와 K만큼 떨어진 인덱스를 똑같이 만들고 만약 K번째 인덱스가 첫번째 인덱스와 같다면, K+1번째 인덱스와 2번째 인덱스를 이것도 같다면, K+2번째와 3번째 인덱스를 같게 만들어 나가면 됩니다.

처음에 통에 담긴 초콜릿 개수가 모두 다른 숫자라는 가정 하에, K-1번 정도 K번째 숫자와 첫번째 숫자를 동일하게 만들고, 오름차순으로 정렬하게되면, K번째 인덱스는 첫번째 인덱스 수와 같아집니다.

K<i, i-K번째 통과 같게 만든 후에, 다시 오름차순으로 정렬하기 때문에, 만약 K번째 인덱스가 첫번째 인덱스와 같다면 1~K 인덱스까지 모든 숫자가 동일하다는 사실을 알 수 있습니다.

이 시점부터, K+1, K+2,K+3번째 숫자를 각각 2,3,4번째 수와 동일하게 만들어가게되고 위 그리디 알고리즘이 맞다는 사실을 밝혀낼 수 있습니다.

[BanApp]

그럼 결론적으로 원래는 K<i인 i를 골라서 I-k번째 통과 맞추면서 해나가야 하는게 맞지만 결국 마지막에는 모든 초콜릿통의 초콜릿의 개수가 arr[0]와 같게 된다. 다만 순서를 바꾸면서 다시 재정렬 하는 과정은 어차피 하루안에 일어나는 일이고 이거는 순서는 바뀔지언정 최종적으로 먹을 수 있는 초콜릿의 최대 개수에 영향을 미치지 않기 때문에 애초부터 arr[0]을 key라는 변수에 놓고 기준값으로 잡고 풀어도 무방하다. 즉 1223 에서 1213을 만들고 1123 으로 재정렬 하나 애초부터 1223에서 가장 가까운 초콜릿통부터 key 변수 기준에 맞춰서 1123으로 만들어서 푸나 우리가 궁금한건 날짜와 먹을 수 있는 초콜릿의 개수 이기 때문에 결론적으로 상관이 없다. 이건가요? 만약에 통에 각각 이름이 붙어서 위와 같은 조건에 통을 구분짓는 문제가 나온다면 위 방법으로는 못풀겠군요,,

[ghdcksgml1]

넹 맞아요. 만약 문제가 그렇게 나올 경우에는 오프라인 쿼리 같은 알고리즘이 필요해서 난이도가 확 오를것같네요

[BanApp]

오우 너무 끔찍하고.. 역시 알고리즘 마스터는 다르십니다ㄷㄷ