2294 동전 2


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
36
37
#include <iostream>
#define INF 987654321
using namespace std;
 
int n, k;
int d[10001];
int a[100];
 
int main() {
 
    scanf("%d%d"&n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d"&a[i]);
        //k보다 큰경우 continue
        if (a[i] > k) continue;
        //그렇지 않은경우 d배열에 1로 초기화
        d[a[i]] = 1;
    }
 
    for (int i = 0; i < n; i++) {
        //k보다 큰경우 continue
        if (a[i] > k) continue;
        //그렇지 않은경우
        for (int j = a[i]+1; j <= k; j++) {
            //d[j-a[i]]==0 ? --> 한번도 갱신되지 않은값에 대해서는 더하지 않는다.
            if (d[j - a[i]] == 0continue;
            //d[j-a[i]] !=0 이고 d[j]가 0이거나 +1한것보다 더 크면 갱신해준다.
            if (d[j] == 0 || d[j] > d[j - a[i]] + 1) {
                d[j] = d[j - a[i]] + 1;
            }
        }
    }
 
    if (d[k] == 0)printf("-1\n");
    else printf("%d\n", d[k]);
}
 
cs


'BOJ::문제풀이' 카테고리의 다른 글

2174 로봇 시뮬레이션  (1) 2018.02.28
5427 불  (0) 2018.02.27
1764 듣보잡  (0) 2018.02.24
9663 N-Queen  (0) 2018.02.24
1949 우수마을  (1) 2018.02.23

+ Recent posts