[백준 C++] 7579 앱 - 다이나믹프로그래밍

7579번: 앱

cpp

#include <iostream>
using namespace std;

int Memory[101];
int Cost[101];
int DP[101][10001];

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(nullptr); cout.tie(nullptr);

‌int N, M;
‌cin >> N >> M;
‌for (int i = 1; i <= N; ++i)
‌{
‌‌cin >> Memory[i];
‌}
‌for (int i = 1; i <= N; ++i)
‌{
‌‌cin >> Cost[i];
‌}

‌for (int i = 1; i <= N; ++i)
‌{
‌‌int Mem = Memory[i];
‌‌int Cst = Cost[i];
‌‌for (int c = 0; c <= 10000; ++c)
‌‌{
‌‌‌if (c >= Cst)
‌‌‌{
‌‌‌‌DP[i][c] = max(DP[i - 1][c], DP[i - 1][c - Cst] + Mem);
‌‌‌}
‌‌‌else
‌‌‌{
‌‌‌‌DP[i][c] = DP[i - 1][c];
‌‌‌}
‌‌}
‌}

‌for (int c = 0; c <= 10000; ++c)
‌{
‌‌if (DP[N][c] >= M)
‌‌{
‌‌‌cout << c;
‌‌‌return 0;
‌‌}
‌}
}

---

 

DP & 배낭 문제입니다.

 

DP[i][c]는 1번 앱부터 i번 앱까지 각 앱을 선택 혹은 미선택하고 누적된 비용이 c일때의

확보된 메모리의 최대값을 저장하도록 했습니다.

 

N번째 앱까지 DP값을 모두 채운 후에는

DP[N][c] 에서 c(누적 비용)를 0부터 1씩 증가시키면서

처음으로 M 이상의 메모리를 확보할 수 있는 비용을 찾아서 출력하도록 했습니다.