白駿解答-ブラックジャック2798号
4572 ワード
📜 理解问题
カジノで最も人気のあるゲームブラックジャックのルールはかなり簡単です.カードと21を超えない限度内で、カード和を最大限に拡大するゲームです.ブラックジャックはカジノごとに異なる規定を持っている.
韓国最高のブラックジャックの達人である金正仁(キム・ジョンイン)氏は、サングン、チャンヨン氏と新しいブラックジャックルールを制定し、ゲームを行う.
金正仁バージョンの黒いジャックには、カードごとに正の整数が書かれています.その後、ディーラーはすべてのN枚のカードを床に置いて、数字を表示します.そしてディーラーはデジタルMを叫んだ.
現在、プレイヤーは限られた時間内にN枚のカードの中から3枚のカードを選ばなければならない.ブラックジャック変形ゲームなので、プレイヤーが選択したカードの和はMを超えず、できるだけMに近づくようにします.
N枚のカードの数字が与えられている場合は、Mを超えずにMに最も近いカード3枚の合計を求めて出力してください.
💡 問題の再定義
Mを超えないカードを3枚探します.
▼▼▼計画作成
三重forゲートで解決できる問題.1つずつ加算して、最大値を選択するのが問題です.このとき重要なのは時間の複雑さです.
カードの個数Nは3<=N<=100である.このとき三重forゲートを回してO(n^3)を大まかに推定し,100の三次方は1000000回の演算である.実際のアルゴリズムは比較したことがないため,これよりはるかに小さい時間複雑度を有するが,100万回の演算は1秒以内に完了するのに十分な時間であるため,ブール関数を用いて行った.
💻 計画の実行
import sys
if __name__ == '__main__':
N, M = map(int, sys.stdin.readline().split())
num_list = list(map(int, sys.stdin.readline().split()))
length = len(num_list)
result = 0
for i in range(length-2):
for j in range(i+1, length-1):
for k in range(j+1, length):
num_sum = num_list[i] + num_list[j] + num_list[k]
if M >= num_sum > result:
result = num_sum
print(result)
🤔 振り返る
時間の複雑さを理解するには、簡単に解決するのが一番早い方法かもしれません.
Reference
この問題について(白駿解答-ブラックジャック2798号), 我々は、より多くの情報をここで見つけました https://velog.io/@delicate1290/백준-문제-풀이-블랙잭-2798번テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol