Skip to content

Instantly share code, notes, and snippets.

@shoken0x

shoken0x/greedy_algorithm.rb

Last active November 19, 2015 02:07
Download ZIP

Revisions

  1. shoken0x revised this gist Nov 19, 2015. No changes.
  2. shoken0x revised this gist Nov 19, 2015. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions greedy_algorithm.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -5,6 +5,8 @@
    $C = [3, 2, 1, 3, 0, 2]
    $A = 620 #620円支払う

    # $A円を支払う最小の硬貨数を求める

    def slove
    ans = 0
    5.downto(0) do |i|
  3. shoken0x created this gist Nov 19, 2015.
    18 changes: 18 additions & 0 deletions greedy_algorithm.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,18 @@
    #input
    $V = [1, 5, 10, 50, 100, 500]

    # 1円玉3枚, 10円玉2枚... 500円玉2枚
    $C = [3, 2, 1, 3, 0, 2]
    $A = 620 #620円支払う

    def slove
    ans = 0
    5.downto(0) do |i|
    t = [$A / $V[i], $C[i]].min
    $A -= t * $V[i]
    ans += t
    end
    puts ans
    end

    slove