ChristmasBatteries

Problem

건전지를 넣어 동작하는 장난감이 있다. 장난감은 총 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번 장난감의 즐거움이다.

Source