[python]白駿16206巻ケーキ(Greedy)

📌 質問する

今日はヒョンの誕生日ジェヒョンは友人N人からケーキをプレゼントしてもらった.ケーキの長さはA 1,A 2,...,ANです.ヒョンでは長さ10のケーキしか食べませんだから、ケーキを切って、できるだけ10インチのケーキを作りたいです.
ケーキは以下の過程で切ることができます.
切るロールケーキを一つ選びます.長さが1より大きいロールケーキしか切ることができません.このとき、均一なケーキの長さをxと呼ぶ.
0より大きい、xより小さい自然数yを選択します.
ロールケーキを長さy,x-yの2つのロールケーキに切ります.
宰鉉はMサイズのケーキを切ることができる.この場合、長さ10のロールケーキ個数の最値を求めるプログラムを作成してください.

入力

第1行は、ロールケーキの個数Nと、切断可能な最大回数Mを与える.(1 ≤ N, M ≤ 1,000)
2行目、ケーキの長さA 1,A 2,...ANが与えられた.(1 ≤ Ai ≤ 1,000)

しゅつりょく

ザイヒョンが作ることができる長さ10のケーキの数の最低価格を輸出する.

入力例1

3 1
10 10 10

サンプル出力1

3

入力例2

3 1
10 10 20

サンプル出力2

4

入力例3

3 3
20 20 20

サンプル出力3

6

入力例4

5 7
10 20 30 40 50

サンプル出力4

11

入力例5

5 8
34 45 56 12 23

サンプル出力5

8

📌 に答える

💬 Code

import sys
input = sys.stdin.readline

n, limit = map(int, input().split())
cake = [int(i) for i in input().split()]

cakeTen = list(filter(lambda x: x % 10 == 0, cake))
cakeNotTen = list(filter(lambda x: x % 10 != 0, cake))

cnt = 0

while limit > 0:
    if cakeTen:
        if cakeTen[0] // 10 - 1 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeTen[0] // 10
            limit -= (cakeTen[0] // 10 - 1)
        del cakeTen[0]

    elif cakeNotTen:
        if cakeNotTen[0] // 10 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeNotTen[0] // 10
            limit -= cakeNotTen[0] // 10
        del cakeNotTen[0]

    else:
        break

print(cnt)

💡 Solution

ケーキは以上の3つのケースに分けることができます.実は長さが10の人は一度も切ったことがなくてケーキをもらいましたが、分けて分類しましたが、30と縛ることができます.

の長いが10の場合:(長さが10)-1回のカット(長さが10)個で

を得る.

長さが10に分ける場合:(長さが10)二次切断(長さが10)個で

を得る.
これでいいんだ!

cake = [int(i) for i in input().split()]

cakeTen = list(filter(lambda x: x % 10 == 0, cake))
cakeNotTen = list(filter(lambda x: x % 10 != 0, cake))

そこで,lambdaを用いて長さ10のケーキ(cakeTen)と落ちないケーキ(cakeNotTen)を別のリストに分類した.
ケーキを切る回数は一定で、ケーキの数を最大限に得るため、ケーキを切る回数の少ないcakeTenが優先されます.

cnt = 0

while limit > 0:
    # 10의 배수 케이크가 남아있으면
    if cakeTen:
        # 케이크가 길어서 많이 자를 수 있는데 커팅횟수 제한에 걸리는 경우
        if cakeTen[0] // 10 - 1 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeTen[0] // 10
            limit -= (cakeTen[0] // 10 - 1)
        del cakeTen[0]

    # 10의 배수 케이크가 없으면
    elif cakeNotTen:
        # 케이크가 길어서 많이 자를 수 있는데 커팅횟수 제한에 걸리는 경우
        if cakeNotTen[0] // 10 > limit:
            cnt += limit
            limit = 0
        else:
            cnt += cakeNotTen[0] // 10
            limit -= cakeNotTen[0] // 10
        del cakeNotTen[0]

    # 모든 케이크를 다 탐색했으면
    else:
        break