商品を購入する際、やり取りするお金の最小の枚数を求める | Codetter（こーどったー）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Arrays;
import java.util.Random;
public class Main {
    public static int turi(int p1, int[] coins) {
        int len = coins.length;
        int[] coin = new int[len];
        System.arraycopy(coins, 0, coin, 0, len);
        Arrays.sort(coin);
        return _turi(Math.abs(p1) % coin[len - 1], Math.abs(p1) / coin[len - 1], len - 2, coin, 0);
    }
    private static int _turi(int p1, int mai, int en, int[] coin, int flag) {
        if(en < 0) return p1 == 0 ? mai: 999999999;
        int a = _turi(p1 % coin[en], mai + p1 / coin[en], en - 1, coin, 0);
        if(flag == 1) return a;
        int b = _turi(coin[en + 1] - p1, mai + 1, en, coin, 1);
        return a < b ? a : b;
    }
/////////////////////////////////////////////////////////////////////////////
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000};
        Random r = new Random();
        for (int i = 0; i < 1000; i++) {
            int kingaku = r.nextInt(100000);
            System.out.println(""+kingaku+"円の支払いやり取り = 最小"+turi(kingaku, coins)+ "枚");
        }
    }
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX