Kickstart2020 RoundA : Allocation

Kickstart 2020 RoundA의 Allocation 문제입니다.

문제.

판매 중인 N사의 가격(i번째 가격은 A i)과 사용 가능한 가젯 B를 제공할 때 최대 몇 곳까지 구매할 수 있도록 한 문제다.
https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7/00000000001d3f56
1\leq B\leq 10^5、1\leq A_i\leq1000, Test set1에서는 1\leqN\leq100, Test set2에서는 1\leqN\leq10^5의 조건입니다.

계산법

직감적으로 가장 싼 물건부터 구매하면 구매 수량이 최대화된다.실제로 이런 생각을 실행에 옮기면 해결 방안을 찾을 수 있다.
가격 명세서를 오름차순으로 정렬하고 처음부터 순서대로 B의 가격을 줄여 B의 마이너스가 끝날 때(B는 0일 때 극한예산 내)까지 기존에 구매한 수량에 필요한 값이다.정렬에서sorted 등을 사용할 때 계산량은 O(NlogN), 1\leqAi\leq1000이 결정되기 때문에 Counting sort를 사용하면 O(n)(count aray의 초기화, 각 값의 계수, 계수의 누적값 계산, 정렬된 그룹의 대입은 N차 순환)이다.

이루어지다

def counting_sort(A):
    max_A = 1000
    counts = [0 for _ in range(max_A + 1)]
    for a in A:
        counts[a] += 1
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]
    sorted_A = [0 for _ in range(len(A))]
    for i in range(len(A) - 1, -1, -1):
        sorted_A[counts[A[i]] - 1] = A[i]
        counts[A[i]] -= 1
    return sorted_A


T = int(input())
for x in range(1, T + 1):
    N, B = list(map(int, input().split()))
    A = list(map(int, input().split()))
    A = counting_sort(A)
    res = 0
    for a in A:
        B -= a
        if B < 0:
            break
        res += 1
    print('Case #{}: {}'.format(x, res))

알고리즘이 구하는 해가 가장 좋다는 것을 증명하다

Analysis에 증명이라고 쓰여 있지만 자세히 이해하지 못했어요...