건전지를 넣어 동작하는 장난감이 있다. 장난감은 총 N개, 건전지는 총 N개다. 장난감 번호는 0에서 N-1이고, i번 장난감은 (i mod 5)개 건전지를 필요로 한다. i번 장난감이 주는 즐거움(fun)의 양은 ((X*i*i + Y*i + Z) mod M)이다. 건전지 N개를 사용해 즐거움을 극대화할 수 있는 장난감 개수를 찾고, 이 때의 즐거움을 반환하라.
Constraints
- B will be between 0 and 7, inclusive.
- N will be between 1 and 10^6, inclusive.
- X, Y, Z will be between 0 and 999, inclusive.
- M will be between 1 and 1000, inclusive.
Code
#include <vector>
using namespace std;
class ChristmasBatteries {
public:
int mostFun(int B, int N, int X, int Y, int Z, int M) {
vector<int> dp (B);
for (int i = 0; i < N; ++i) {
int ib = i % 5, fun = (1ll*X*i*i + 1ll*Y*i + Z) % M;
for (int j = B; j >= ib; --j) {
dp[j] = max(dp[j], dp[j-ib]+fun);
}
}
return dp[B];
}
};
Explanation
0번부터 N-1번까지 장난감을 탐색하면서, dp[j]와 dp[j-ib]+fun 중 최대값을 dp[j]에 저장한다. dp[j-ib]는 (i 이전에 찾은) 건전지 j-ib개를 사용한 장난감의 최대 즐거움이다. fun은 건전지 ib개를 사용해 얻은 i번 장난감의 즐거움이다.
최근 덧글