[Swift]伯俊11047-硬貨0

1308 ワード
greedy swift テキストリンク

Greedyアルゴリズム


それぞれの選択の瞬間は、目の前の最適な選択だけをして、最終的な答えを達成するアルゴリズムです.
(これらの選択の結果が常に最適であることは保証できないが、階調アルゴリズムを適用する問題では最適である.)

例えば?


最小値を見つけるツリー構造があるとします.
      3
     
   4     2

1    6  5   10
ツリーが次のように表示される場合
グリディアルゴリズムは3−>2−>5を経て,5を最小値と判別した.
この例では、実際の最小値は1であるが、GRADYアルゴリズムでは、現在の最適選択は常に最適値であることが保証されるため、これは問題ではない.

白駿11047-硬貨0


問題のショートカット

に答える


これはグリディアルゴリズムを用いた代表的な問題である.
作るK元より小さいコインの中から一番大きい値を選べばいいです.

最終コード


import Foundation

let line = readLine()!.split(separator: " ").map{Int(String($0))!}
let N = line[0]
var K = line[1]
var coinArr = Array(repeating: 1000000, count: 10)

for i in 0..<N {
    let coinValue = Int(readLine()!)!
    coinArr[i] = coinValue
}

var count = 0

for i in (0..<N).reversed() {
    let nowCount = K / coinArr[i]
    K -= nowCount * coinArr[i]
    count += nowCount
    
    if K == 0 {
        break
    }
}
print(count)
  • の高額から探すので逆()を使います.
  • coinAr[i]の値がKより大きくても、nowCountの値が0の場合は、心配する必要はありません.
    • react-queryバー
    プログラマーコードテスト「模擬試験」