챕터11_섹션1_탐욕 알고리즘

#include <cstdio>

int main()

{

int t, e, f, realMem, n, mem[10001], *appTime, *appMem;

scanf("%d", &t);

for (int i = 0; i < t; ++i)

{

for (int j = 1; j < 10001; ++j)

mem[j] = 500000000;

mem[0] = 0;

scanf("%d %d %d", &e, &f, &n);

realMem = f - e;

appTime = new int[n];

appMem = new int[n];

for (int j = 0; j < n; ++j)

scanf("%d %d", &appTime[j], &appMem[j]);

for (int j = 0; j < n; ++j)

for (int k = 0; k <= realMem; ++k)

if (mem[k] + appTime[j] < mem[k + appMem[j]])

mem[k + appMem[j]] = mem[k] + appTime[j];

delete[] appTime;

delete[] appMem;

(mem[realMem] == 500000000) ? printf("-1") : printf("스마트폰의 최소 실행 시간 : %d\n", mem[realMem]);

}

}