Easy is Perfect

[백준] 2178번 C/C++ 풀이 _ 미로 탐색

  • melonicedlatte
  • Jul 05, 2018


- 출처 : https://www.acmicpc.net/problem/2293 


동전 1 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초4 MB152216241462940.393%

문제

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

입력

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

출력

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

예제 입력 1 

3 10
1
2
5

예제 출력 1 

10

출처

알고리즘 분류



- 문제 풀이

dp 를 사용하는 문제이다.
간만에 풀어서 너무 헤맸다. 

http://debuglog.tistory.com/78 에 상세한 풀이가 기재되어 있다. 

- 소스 코드

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
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <vector>
#pragma warning(disable : 4996)
 
using namespace std;
 
int n, k;
vector<int> coin_vec;
vector<int> dp;
 
int main() {
    scanf("%d %d", &n, &k);
    dp.resize(k + 1, 0);
 
    for (int get_num = 0; get_num < n; get_num++) {
        int sub_num;
        scanf("%d", &sub_num);
        coin_vec.push_back(sub_num);
    }
 
    sort(coin_vec.begin(), coin_vec.end());
 
    dp.at(0) = 1;
 
    for (int vec_flag = 0; vec_flag < coin_vec.size(); vec_flag++) {
        for (int search_flag = 1; search_flag <= k; search_flag++) {
            if (search_flag >= coin_vec.at(vec_flag) )
                dp.at(search_flag) += dp.at(search_flag - coin_vec.at(vec_flag));
        }
    }
 
    printf("%d", dp.at(k));
    return 0;
}
cs



Search