티스토리 뷰

알고리즘/BOJ

BOJ 2293번, 동전 1

아테즈 2018. 10. 20. 20:58

유명하고, 간단한 DP문제입니다. 


가치가 X원이 되는 모든 경우의 수를 A(x)라고 했을 때,


입력받은 동전이 1, 2, 5원이고 10원을 만든다고 하면 (예제 1)


A(10)은 A(9)+1원, A(8)+2원, A(5)+5원이라고 할 수 있고,


A(9) = A(8) + A(7) + A(4)

A(8) = A(7) + A(6) + A(3)

A(5) = A(4) + A(3) + A(0)  

 cf) A(0)=1

...


이런식으로 여러가지의 점화식이 생깁니다.


중복되는 항이 많으므로, Dynamic Programming 기법을 사용해 문제를 풀면 아래의 소스코드와 같이 풀 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
 
using namespace std;
 
typedef long long LL;
LL N, K;
 
LL method[10001];
 
int main(){
    cin >> N >> K;
 
    method[0= 1;
    for (int i = 0; i < N; i++) {
        int coin;
        cin >> coin;
 
        for (int j = coin; j <= K; ++j)
        {
            method[j] += method[j - coin];
        }
    }
 
    cout << method[K];
    return 0;
}
cs


'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 14731번, 謎紛芥索紀 (Large) - (미분개색기)  (0) 2018.10.20
BOJ 11047번, 동전 0  (0) 2018.10.20
BOJ 2294, 동전 2  (0) 2018.10.20
BOJ 14754, Pizza Boxes  (0) 2018.10.20
BOJ 1697, 숨바꼭질  (0) 2018.10.20
댓글
댓글쓰기 폼
공지사항
Total
23,335
Today
0
Yesterday
10
링크
TAG
more
«   2022/11   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30
글 보관함