[BOJ] 2293번 : 동전 1

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n, k; 
int a[105];
int d[10005]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> k; 
	for (int i = 0; i < n; i++) cin >> a[i]; 
	d[0] = 1; 
	for (int i = 0; i < n; i++) {
		for (int j = a[i]; j <= k; j++) {
			d[j] += d[j - a[i]];
		}
	}
	cout << d[k] << '\n';
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x10/solutions/2293.cpp

basic-algo-lecture/0x10/solutions/2293.cpp at master · encrypted-def/basic-algo-lecture

 

dp를 이용해서 풀었다. 따라서, 세 가지 스텝을 따른다. 

1. 테이블을 정의한다. d [i] = i라는 금액을 만드는 경우의 수 

2. 점화식을 작성한다. d [i] = d [j-a [i]] 

3. 초기값을 설정한다. d [0] = 1 

1,2,5 
d[0] = 0 --> 1
d[1] = 1 -->1
d[2] = 11, 2 -->2
d[3] = 111, 21, -->2
d[4] = 1111, 211, 22  -->3
d[5] = 11111, 2111,221,5  -->4
d[6] = 111111,21111,2211,51,222 --> 5 
d[7] = 1111111,211111,22111,511,2221,52 -->6 
d[8] = 11111111,2111111,221111,5111,22211,521,2222 --> 7 
d[9] = 111111111,21111111,2211111,51111,222111,5211,22221,522 --> 8 
d[10] = 1111111111,211111111,22111111,511111,2221111,52111,222211,5221,22222,55 -->10

콘셉트가 아직 완전히 이해가 가지는 않는다. 하지만, 이해가 가는 것 같기도 하다. 시간이 약이다.