[BOJ 2293] 동전 1

문제 링크 : https://www.acmicpc.net/problem/2293

문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

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

출력

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

제한

시간 제한	메모리 제한
0.5sec (추가 시간 없음)	4MB

---

풀이

예제를 보며 이해해보자. 사용할 수 있는 동전은 1원, 2원, 5원짜리 동전이며, 우리는 총 10원을 만드는 방법을 세려 한다. 사용한 동전의 구성이 같으면 1번만 센다고 하였으니, 10원을 만드는 경우의 수를 찾아보면 아래와 같다.

번호	경우의 수
1	1원 x 10개
2	2원 x 1개 + 1원 x 8개
3	2원 x 2개 + 1원 x 6개
4	2원 x 3개 + 1원 x 4개
5	2원 x 4개 + 1원 x 2개
6	2원 x 5개
7	5원 x 1개 + 1원 x 5개
8	5원 x 1개 + 2원 x 1개 + 1원 x 3개
9	5원 x 1개 + 2원 x 2개 + 1원 x 1개
10	5원 x 2개

동전의 종류가 3개밖에 없는데도 예제의 정답이 $10$가지가 나온다. 이런 방식으로 정답을 찾아가는 것은 무리일 것 같다. 해결할 수 있는 방법을 고민해보면서 아래와 같은 정보를 얻었다.

• 가장 큰 단위인 5원을 기준으로 생각해보자. 10원을 만들기 위해 5원을 최대 2번까지 사용할 수 있으며, 5원을 각각 0번, 1번, 2번 사용하는 경우를 모두 세는 것을 볼 수 있다
  • 5원을 2번 사용한 경우, 남은 0원을 만들기 위한 고민을 해야한다
  • 5원을 1번 사용한 경우, 남은 5원을 만들기 위한 고민을 해야한다
  • 5원을 0번 사용한 경우, 남은 10원을 만들기 위한 고민을 해야한다

이렇게만 보면 냅색 알고리즘을 사용해야할 것 같다. 하지만 시간도 부족해보이고, 무엇보다 메모리 제한이 살인적이다. 다행히도, 현재 상황을 처리하면 남은 상황은 원래 문제의 subproblem인 것 처럼 보인다. 해서, 냅색 알고리즘에서 다이나믹 프로그래밍의 아이디어만 살짝 가져와서 문제를 해결해보자.

동전을 이용해 만들 수 있는 가치와 동전의 가치를 합치면, 새로운 가치를 만들어낼 수 있다. 점화식으로도 풀이가 가능하다. 그리고, 점화식으로 풀이가 가능하다는 것은 대부분 dp문제로 해석될 수 있다는 뜻이다. 점화식은 아래와 같이 세울 수 있을 것이다.

\[dp[i] = \sum dp[i-j]\]

이 때 $j$는 문제에서 주어질 수 있는 동전의 가치들이다. 현재 가치가 $7$인데 사용하는 동전의 가치가 $4$라면 우리는 더하여 가치가 $11$인 경우를 만들어낼 수 있다. 이 논리대로 점화식을 코드로 풀어내면 답을 얻을 수 있다.

소스코드

Github Link : Source Code

참고 알고리즘 : 다이나믹 프로그래밍