# [Gold I] 롤러코스터 타기 [문제 링크](https://www.acmicpc.net/problem/3958) ## 문제 설명 <p>상근이와 친구들은 놀이 공원에 놀러갔다. 이 놀이 공원에는 많은 종류의 롤러코스터가 있고, 상근이는 각 롤러코스터를 미리 분석해 왔다. 상근이는 각 롤러코스터를 탔을 때 느낄 수 있는 재미를 숫자로 적어왔다. 하지만, 롤러코스터를 탈 때 마다 느끼는 재미는 점점 떨어진다.</p> <p>상근이는 i번 롤러코스터를 k번째로 탔을 때 느끼는 재미를 함수로 정의해 왔다. f(i, k) = a_i - (k-1)²*b_i. 만약 f(i,k)값이 양수가 아니라면, 그 롤러코스터를 타면, 더이상 재미를 느끼지 않는 것이다.</p> <p>상근이는 재미의 합이 최대가 되게 롤러코스터를 타려고 한다.</p> ## 입력 <p>첫째 줄에 N이 주어진다. N은 놀이 공원에 있는 롤러코스터의 개수이다. (0 < N ≤ 100)</p> <p>다음 N개의 줄에는 a_i, b_i, t_i가 있다. a_i와 b_i는 상근이가 정의한 함수의 계수이고, t_i는 i번째 롤러코스터를 타는데 걸리는 시간이다. (0 ≤ a_i, b_i ≤ 1,000, 0 < t_i ≤ 25,000)</p> <p>다음 줄에는 놀이 공원을 방문하는 시간의 개수 Q가 주어진다. (0 ≤ Q ≤ 1,000) 다음 Q개 줄에는 상근이가 놀이 공원에 방문하는 시간 T_i가 주어진다. (0 ≤ T_i ≤ 25,000)</p> ## 출력 <p>출력은 Q개의 줄을 출력한다. 각각의 시간 T_i에 대해서, 상근이가 느낄 수 있는 최대 재미 점수를 출력한다.</p> ## 풀이 * b=0인 경우 항상 a씩 재미가 늘어나니 중복을 허용하는 냅색으로 구현. * 나머지는 k번째의 재미를 미리 계산하여 중복을 허용하지 않는 냅색으로 구현. ``` c++ #include<bits/stdc++.h> using namespace std; const int MAX = 25'000; int dp[MAX+1]; // i초까지의 최대 재미 int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; while(n--) { int a, b, t; cin >> a >> b >> t; if(b==0) { // b=0인 경우 예외 처리 for(int i=0;i+t<=MAX;i++) dp[i+t] = max(dp[i+t], dp[i]+a); } else { int curT=t, k=1, curFun=a; while(curT<=MAX && curFun>0) { for(int i=MAX;i-t>=0;i--) dp[i] = max(dp[i], dp[i-t]+curFun); curT += t; k++; curFun = a-(k-1)*(k-1)*b; } } } int q; cin >> q; while(q--) { int t; cin >> t; cout << dp[t] << '\n'; } } ```