[WEEK04] DAY27, 28
1918 ワード
DAY27
2021.11.27 SAT
日曜日まですべてブラウズ
月曜日のすべての問題を正しく理解する(チームコメント)
火曜日水曜日にアルゴリズムのテーマを復習します
ここで、「通常、ソート(Sort)技術は、極端な問題を処理するために使用され、例えば、デフォルトでは無条件に大きく、無条件に小さく、無条件に長く、または無条件に短く処理される.」この文章を読めば分かります.あ、だから並べ替えは一緒に従うんですね.
グリディアルゴリズム>結局、私が考えている問題解決方法は最善の解決方法ではないと思いますか?私は一人で何が一番いいかをどう判断するか考えています.
そしてコーチは返事をした.
「それが一番だと言いたいなら、他の方法が一番ではないことを証明しなければなりません」
.
.
DAY28
2021.11.28 SUN
コイン問題の解決
9084硬貨（DP）
コード#コード#
import sys
input = sys.stdin.readline
testcase = int(input())
for _ in range(testcase):
n = int(input())
coins = list(map(int, input().split()))
m = int(input())
dp = [0] * (m + 1)
dp[0] = 1
for coin in coins:
for i in range(m + 1):
# a_(i-k) 를 만드는 방법이 존재한다면
# 이전 경우의 수에 현재 동전으로 만들 수 있는 경우의 수를 더한다.
if i >= coin:
dp[i] += dp[i - coin]
print(dp[m])11047硬貨0(グリディ)
この問題は正しく読めば簡単だ
コード#コード#
import sys
n, money = map(int, sys.stdin.readline().split())
coins = []
for _ in range(n):
coins.append(int(sys.stdin.readline()))
coins.sort(reverse=True)
count = 0
for coin in coins:
if coin == 0:
break
count += money // coin
money = money % coin # 남은 잔액
print(count)Kがコインより金額が小さいと大きな金額から回るのは効率的ではありません.
Kがコインより小さい場合はcontinue(passまたはpop)の条件をつけたほうがいいです.
Reference
この問題について([WEEK04] DAY27, 28), 我々は、より多くの情報をここで見つけました https://velog.io/@yerimii11/WEEK04-DAY27テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol