つり銭

/* infinite amount of coin 있을 때
거스름돈을 줄 수 있는 방법의 수 구하기.
dynamic programming을 이용해 해결할 수 있다.
동전 제거한 값 + 동전 포함한 값
*/

public class Main
{
	public static void main(String[] args) 
	{
	    int[] coins = {2,3,5,10}; // 갖고 있는 동전의 종류
	    int w = 15; // 거스름돈이 15원이라고 했을 떄
	    int[][] arr = new int[coins.length][w+1]; // 누적 결과 테이블
	    // 각 동전
	    arr[0][0] = 1; // 0원일때는 1가지 방법. (동전을 안 쓴다)
	    for (int i=1; i<16; i++)
	    {
	       if (i % 2 == 1)
	            arr[0][i] = 0;
	       else
	            arr[0][i] = 1;
	    }
	    
	    for (int i=1; i<coins.length; i++)
	    {
	        arr[i][0] = 1;
	        for (int j=1; j<w+1; j++)
	        {
	           if (coins[i] > j) // 해당 동전보다 거스름돈이 작으면 
	           // above값 그대로.
	                arr[i][j] = arr[i-1][j]; // above value
	           else // above값 + exclude한 값.
	                arr[i][j] = arr[i-1][j] + arr[i][j-coins[i]];
	        }
	    }
	    
	    for (int i=0; i<coins.length; i++)
	    {
	        for (int j=0; j<w+1; j++)
	        {
	            System.out.print(arr[i][j]+" ");
	        }
	        System.out.println();
	    }
	    // 테이블 마지막 원소가 답.
	}
}

public class Main
{ 
    public static int func(int[] coin, int n)
    { // 동적 계획. 누적 값 넣을테이블 만들기
        int[] ans = new int [n+1];
        ans[0] = 0;
        // coin = {1,3,4}
        //ans[1] = 1;
        //ans[3] = 1;
        //ans[4] = 1;
        
        for (int i=0; i<coin.length; i++)
        {
            ans[coin[i]] = 1;
        }
        
        for (int i=1; i<=n; i++)
        {
            int temp = Integer.MAX_VALUE;
            for (int j=coin.length-1; j>=0; j--)
            {
                if (i-coin[j] >=0)
                {
                    ans[i] = Math.min(temp, ans[coin[j]] + ans[i-coin[j]]);
                    temp = ans[i];
                }
            }
        }
        return ans[n];
    }
    
    
    public static void main(String[] args)
    {
        int[] arr = {1,3,4};
        System.out.println(func(arr, 15));
    }
}