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]] == 0) continue; //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 |