GreedyChange

Code

import java.util.Arrays;

public class GreedyChange

{

    public int smallest(int[] denoms) {

        Arrays.sort(denoms);

        

        int max = denoms[denoms.length-1]*2;

        int[] mins = new int[max+1];

        for (int i=1; i<=max; i++)

            mins[i] = 9999999;

        for (int i=1; i <= max; i++)

            for (int j=0; j < denoms.length; j++)

                if(denoms[j] <= i)

                    mins[i] = Math.min(mins[i], 1 + mins[i-denoms[j]]);

        int index=0;

        for (int i=1; i <= max; i++) {

            while (1+index < denoms.length && denoms[1+index]<=i)

                index++;

            if (mins[i] != 1+mins[i-denoms[index]])

                return i;

        }

        return -1;

    }

}

Explanation

최소값 알고리즘

mins[i] = Math.min(mins[i], 1 + mins[i-denoms[j]]);

탐욕 알고리즘 (Greedy Algorithm)

while (1+index < denoms.length && denoms[1+index]<=i) index++;

References

https://community.topcoder.com/stat?c=problem_solution&cr=157974&rd=4474&pm=1579