[Algorithm]Baekjoon 7579 :: 앱

https://www.acmicpc.net/problem/7579

7579번: 앱

 
int n, m, input;
int usingMemories[101] = { 0 };
int deActivateCosts[101] = { 0 };
int dp[101][10001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> usingMemories[i];
    }
 
    int sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> deActivateCosts[i];
        sum += deActivateCosts[i];
    }
 
    dp[0][0] = 0;
    int answer = 0x3f3f3f3f;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= sum; ++j)
        {
            if (deActivateCosts[i] <= j)
            {
                dp[i][j] = max(dp[i - 1][j], usingMemories[i] + dp[i - 1][j - deActivateCosts[i]]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
 
            if (dp[i][j] >= m)
            {
                answer = min(answer, j);
            }
        }
    }
 
    cout << answer;
}
 
 
 
 

 

배낭문제랑 비슷한 느낌이 났는데, 그렇다고 그걸 그대로 대입하려하면 안된다. 왜냐하면 m값이 최대 천만이기 때문에 그대로 적용하려하면 메모리도 초과되고 시간도 초과된다.

 

해결법은 역발상이다. 기준을 비용으로 잡고 dp테이블을 업데이트한다.

즉, dp[i][j]는 i번째 프로그램까지를 따졌을 때, j비용으로 비활성화 시킬 수 있는 최대 메모리이다.