📝 문제 정보#
🧐 관찰 및 접근#
- 댐에 수문이 있고, 유량과 피해비용이 있는 것 같다.
- 피해비용은 여는 시간에 비례하지 않는 것 같다.
- 그러면 각 수문에 대해, 유량에 시간을 곱해서 각 수문이 버릴 수 있는 물의 양을 구할 수 있고, 그에 따른 가격이 나온다.
- 이건 그리디하게는 조금 곤란하고, 배낭 문제로 되나? 했는데, $V$가 너무 크다!
- 그런데 수문의 개수가 $n \leq 20$으로 유의미하게 작다. 각 테스트케이스에 대해 모든 수문을 열어보는 경우의 수를 수행할 수 있을 것 같다.
- 시간복잡도 $O(2^n \cdot nm)$ 정도에 동작할 것 같다.
💻 풀이#
- 코드 (C++):
void solve(){
int N; cin >> N;
vector<pll> door(N);
rep(i, 0, N) cin >> door[i].first >> door[i].second;
int Q; cin >> Q;
rep(q, 1, Q+1){
ll V, T; cin >> V >> T;
ll ans = 1e18;
rep(bit, 0, 1<<N){
ll wat = 0, cost = 0;
rep(i, 0, N) if(bit & (1<<i)) wat += door[i].first*T, cost += door[i].second;
if(wat >= V) ans = min(ans, cost);
}
cout << "Case " << q << ": ";
if(ans == 1e18) cout << "IMPOSSIBLE\n";
else cout << ans << '\n';
}
}