[백준] 7579번 - 앱 (C++) 문제 및 풀이

문제) 백준 - DP(동적 계획법) - 앱

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

7579번: 앱

 

메모리를 memoization을 진행하면 메모리 초과로 터진다.

dp[idx][Cost]: Cost로 idx번째 앱에서 얻을 수 있는 최대 메모리를 계산한다. Cost를 0부터 증가시켜 M보다 클 경우 break 하여 출력한다. 

 

 

C++ 소스코드)

	int solve(int idx, int C) {
	if (idx == N) return 0;
	int& ret = cache[idx][C];
	if (ret != -1) return ret;
	//활성화
	ret = solve(idx + 1, C);
	//비활성화
	if (C >= cost[idx])
	ret = max(ret, solve(idx + 1, C - cost[idx]) + memory[idx]);
	return ret;
	}

view raw 7579.cpp hosted with ❤ by GitHub

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/7579_%EC%95%B1.cpp

GitHub - Chocochip101/BOJ_Solution