# [Gold II] 훈련 [문제 링크](https://www.acmicpc.net/problem/31265) ## 문제 설명 <p>작전과장 승서는 부대의 24-1분기 훈련 계획을 구성하여야 한다. 이를 위해 승서는 훈련 계획에 포함할 훈련들을 선정해야 한다.</p> <p>훈련은 $N$가지의 훈련 상황으로 분류되어 있으며, $i$번째 훈련 상황은 $d_i$개의 훈련으로 이루어져 있다. $i$번째 훈련 상황의 $j$번째 훈련에 소요되는 시간은 $t_{ij}$이다.</p> <p>승서는 모든 상황에 대해 완벽한 대비를 하고 싶기 때문에 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣으려고 한다. 또한, 훈련 계획에 포함된 훈련들의 시간 총합은 $M$시간을 초과할 수 없으며 각 훈련은 한 번만 진행할 수 있다.</p> <p>완벽한 전투대비태세 유지를 위해, 승서는 위 조건 아래에서 훈련 시간의 총합이 최대가 되도록 훈련 계획을 구성하고자 한다. 조건을 만족하는 최대 훈련 시간을 구해 국군 장병들의 완벽한 전투대비태세 유지를 도와주자.</p> ## 입력 <p>첫 번째 줄에 훈련 상황의 가짓수 $N$, 최대 훈련 시간 $M$이 공백으로 구분되어 주어진다.</p> <p>두 번째 줄에 각 훈련 상황에 속한 훈련의 개수를 의미하는 $N$개의 정수 $d_1, \cdots, d_N$이 공백으로 구분되어 주어진다.</p> <p>이후 $N$개의 줄에 걸쳐 $i+2$번째 줄에 $i$번째 훈련 상황에 속한 훈련의 소요 시간을 나타내는 $d_i$개의 정수 $t_{ij}$가 공백으로 구분되어 주어진다.</p> ## 출력 <p>조건을 만족하는 최대 훈련 시간을 구하여라.</p> <p>만약 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣는 것이 불가능하다면 <span style="color:#e74c3c;">-1</span>을 출력한다.</p> ## 제한 <ul> <li>$1 \le N \le 1\,000$</li> <li>$1 \le M \le 10\,000$</li> <li>$1 \le d_i \le 1\,000$; $\sum\limits_{i=1}^N d_i \le 1\,000$</li> <li>$1 \le t_{ij} \le 1\,000$</li> <li>모든 입력은 정수이다.</li> </ul> ## 풀이 #### 전체 $d_i$의 합이 최대 1000이었기에 $Md$가 시간 안에 돌아 냅색으로 풀었다. ``` c++ #include<bits/stdc++.h> using namespace std; int cnt[10'001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; vector<int> d(n+1); for(int i=1;i<=n;i++) cin >> d[i]; memset(cnt, -1, sizeof cnt); cnt[0]=0; for(int i=1;i<=n;i++) { while(d[i]--) { int t; cin >> t; for(int j=m;j-t>=0;j--) { if(cnt[j-t]>=i-1) cnt[j]=i; } } } for(int i=m;i>0;i--) { if(cnt[i]==n) { cout << i; return 0; } } cout << -1; } ```