dp를 이용해 구할 수 있다.
https://www.youtube.com/watch?v=L27_JpN6Z1Q
/* 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));
}
}