[백준/c++] 2293번 - 동전1

문제

https://www.acmicpc.net/problem/2293

문제

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

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

입력

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

출력

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

풀이과정

1.규칙

• dp이므로 점화식과 메모이제이션을 이용합니다.
• 경우의 수는 최대 $2^{31}$ 입니다.
• n가지 종류의 동전을 사용해서 그 가치의 합이 k가 되도록 합니다. 각각의 동전은 몇개라도 사용할 수 있습니다.

2.순서

경우의 수는 최대 $2^{31}$ 이므로, -2,147,483,648 ~ 2,147,438,647의 범위를 갖는 int를 사용합니다.

가치(k)는 4, 동전의 종류(n)는 1,2,3인 경우를 메모이제이션으로 생각해보면,

	coin[1]=1	coin[2]=2	coin[3]=3	총 경우의 수
1	1 (1가지)	0	0	1가지, d[1]=1
2	1+1 (1가지)	2 (1가지)	0	2가지, d[2]=2
3	1+1+1 (1가지)	2+1 (1가지)	3 (1가지)	3가지, d[3]=3
4	1+1+1+1 (1가지)	2+2 (2가지)	3+1 (1가지)	4가지, d[4]=4

의 순서로 진행되어 4라는 정답이 나오게 됩니다.

d[0]=1로 초기화해준 뒤,

빨간색행을 i로, 보라색열을 j로 생각해보면  j - i 가 0 이상일경우, 총 경우의 수가 d[j-coin[i]]씩 증가함을 알 수 있습니다.

예를들어,

j : 2, i : 2일때 d[2-coin[2]]=d[0]=1 이므로 d[1]+d[0]=2,

j : 4, i : 2일때 d[4-coin[2]]=d[2]=2 이므로 d[1]+d[2]=3,

j : 4, i : 3일때 d[4-coin[3]]=d[1]=1 이므로 d[1]+d[2]+d[1]=4

가 됩니다.

결국 점화식은

(i : 1~n), (j : 0~k) 이고, j-coin[i] >=0 일때 d[j] += d[j-coin[i]] 가 됩니다.

3.코드