1049ギター弦

質問する

Day Of MorningのギタリストKantoが使用している その他 N行 切れた.そのため、新しい行を購入または交換する必要があります.疆土はできるだけお金を少なくします. 6行セットを買うこともできますし、1つ以上の単行セットを買うこともできます.
1つのプログラムを作成して、プログラムの中で切れた他の行数Nと他の行ブランドM個、各ブランドが販売する他の行数6個のパッケージの価格、および単独で購入する時の価格を与える時、少なくともN個を買うのに最小限のお金がかかります.

入力

1行目はNとMです.Nは100以下の自然数、Mは50以下の自然数である.2行目から、M行では、各ブランドの包装価格と単一価格が空白に区分される.価格は0以上、1000以下の整数です.

しゅつりょく

最初の行 少なくともN本のギター弦を購入するのに必要な資金の最高価格を印刷します.

N,M = map(int,input().split())

package = []
single = [] 

for i in range(M):
    a,b = map(int,input().split())
    package.append(a)
    single.append(b)

package_min = min(package)
single_min = min(single)

#single의 단가가 더 비쌀 때
if package_min < single_min*6:
    # 6으로 나누어 떨어지지 않는 나머지 값을 계산하려 할 때, 패키지 값보다 낱개 값이 더 비싸면 "패키지 값 선택" 
    if package_min < (N%6)*single_min:
        print((N//6)*package_min+package_min)
    else: 
        print((N//6)*package_min+(N%6)*single_min)

#package의 단가가 더 비쌀 때
elif package_min >= single_min:
    print(N*single_min)

に感銘を与える
これは容易な問題であるが,短時間ではすぐに実現しなかった.
数学の思考と表現力にまだ欠けているようだ.
軽率にNaiveで計算(もちろんGredy問題)するよりも、問題の中で何が要求されているのか、核心的な考え方(単価で比較)を指摘します.
GRADY問題でも,ある程度の数学的思考に基づいて論理を立てる.