백준 2293 c

#include <stdio.h>
#include <stdlib.h>

#pragma warning(disable:4996)

int input(int lower, int upper)
{
	int A;

	while (1)
	{
		scanf("%d", &A);
		if (A >= lower && A <= upper)
		{
			break;
		}
		else
		{
			;
		}
	}

	return A;
}

void input_arr(int* arr, int n)
{
	int i;

	for (i = 0; i < n; i++)
	{
		arr[i] = input(1, 100000);
	}

	return;
}

int main(void)
{
	int n, k, i, j;
	int coin[100];
	int* dp;

	n = input(1, 100);
	k = input(1, 10000);
	input_arr(coin, n);
	dp = (int*)malloc(sizeof(int) * 100001);//동전의 가장 큰 가치만큼 돌아야함
	if (dp == NULL)
	{
		return -1;
	}
	for (i = 0; i <= k; i++)
	{
		dp[i] = 0;
	}
	dp[0] = 1;
	for (i = 0; i < n; i++)
	{
		for (j = coin[i]; j <= k; j++)
		{
			dp[j] = dp[j] + dp[j - coin[i]];
		}
	}
	printf("%d\n", dp[k]);

	/*for (i = 0; i <= k; i++)
	{
		printf("%d ", dp[i]);
	}
	printf("\n");*/

	free(dp);

	return 0;
}