CodeDrive

n가지 종류의 동전이 있따. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

첫째 줄에 n, k가 주어진다. (1<=n<=100, 1<=k<=10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100.000보다 작거나 같은 자연수이다.

첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다.

대표적인 동적계획법으로 풀어야 하는 문제이다. 점화식은 다음과 같이 나타낼 수 있다. 

 

dp[i]=dp[i-coins]

즉 예시로 보면 dp[i]=dp[i-1]+dp[i-2]+dp[i-5] 인 것이다.

하지만, 동전의 갯수는 최대 100개까지 주어질 수 있으므로 너무 많은 호출이 발생한다. (stackoverflow)

따라서 이를 해결하기 위해서 메모리제이션 방법을 사용하도록 한다.

자연수 N과 정수 K가 주어졌을 때 이항 계수 (N, K)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

첫째 줄에 N과 K가 주어진다. (1<=N<=1,000, 0<=K<=N)

(N, K)를 10,007로 나눈 나머지를 출력한다.

N의 크기가 커짐에 따라서 더 이상 이항계수 문제를 재귀적방법으로 해결할 수 없다. 일반적으로 재귀함수가 가독성이 좋긴 하지만 동일한 함수를 자주 호출하다보니 N이 커질수록 stack overflow가 발생할 수 있다. 따라서 이를 해결하는 방법으로 dp (메모리제이션) 을 사용한다. 작은 값의 함수들 부터 배열에 값을 저장하면서 원하는 값까지 진행을 하는 방식이다. 

따라서 이항계수1 문제와 풀이는 비슷하나 함수를 호출하는 것이 아닌 배열의 값을 호출한다는 차이가 있다.