単位 [Kotamanegi Online Judge No.68]

https://kotamanegi.com/Problems/view/index.php?page=68

解説

https://kotamanegi.com/Submission/view/index.php?SubmissionID=1538

受講の最適解を考える。
取得単位数が多い科目から順に使っていくのが最適。
取得単位数が多い順で取っていって、M単位以上となったときの科目数が答え。
M=0のときは0科目が答えとなるので注意。

int N, M, A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N, greater<int>());

    if (M == 0) {
        printf("0\n");
        return;
    }

    int sm = 0;
    rep(i, 0, N) {
        sm += A[i];
        if (M <= sm) {
            printf("%d\n", i + 1);
            return;
        }
    }
}