📝 문제 정보#
🧐 관찰 및 접근#
- 이해가 조금 어려운데, 결국 $N$개의 훈련 상황에서 $d$개의 훈련 가운데 하나를 계속 고르고, 훈련 시간의 합을 최대화 하고싶다.
- 배낭 문제와 비슷해보인다.
- $d$개의 선택지가 $N$번 주어지고, 훈련시간 = 무게의 합을 최대화 해야한다.
- 어? 나이브하게 하면 터지나?
- 각 단계마다 해야하는 연산량은 $M * d_i$이다.
- 총 연산량은 $\sum\limits_{i = 1}^N M * d_i \leq 1000 M$ 이니 괜찮을 것 같다.
- 아니!!!!!!!! 왜틀렸나 했네
- 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣으려고 한다.
- 한 훈련을 여러번 쓰지 않게 $M$에 대해 역순으로 돌면서, 잘 처리하자.
💻 풀이#
- 코드 (C++):
void solve(){
cin >> N >> M;
rep(i, 0, N){
cin >> D[i];
tv[i].resize(D[i]);
}
rep(i, 0, N) rep(j, 0, D[i]) cin >> tv[i][j];
knapsack[0][0] = true;
rep(i, 1, N+1) for(auto t: tv[i-1]) rrep(j, 0, M+1) if(j - t >= 0 && (knapsack[i-1][j-t] || knapsack[i][j-t])) knapsack[i][j] = true;
rrep(j, 0, M+1) if(knapsack[N][j]){
cout << j;
return;
}
cout << -1;
}