알고리즘은 다음과 같습니다.

입력되는 메모리,비용값을 각각 길이 N짜리 배열 m,c에 담습니다.

이때 (m[i],c[i])는 i번째 앱의 정보를 나타냅니다.

d[n][c]= 입력값 배열의[0:n]구간의 앱을 임의로 골라,  비용 c로 얻을수 있는 메모리의 최댓값

으로 정의합니다.

여기서

d[n][c]가 주어지면 d[n+1][?]을 구할수 있음을 이용합니다.

d[n][c]값, 즉 [0:n]구간에서 비용 C로 얻을수 있는 최대의 값을 알고 있으니, 이를 이용해서 만들수 있는 경우는 다음 두가지입니다.

i) 입력 배열의 n+1번째 앱을 고르는경우

이경우 c[n+1]의 비용을 추가로 들여, d[n][C]+m[n+1]만큼의 메모리를 얻을 수 있습니다.

따라서 이 값을 d[n+1][C+c[n+1]]로 간주할수 있습니다.

원래 있던 값과 비교해 더 큰값을 계산하여, 메모리의 최댓값을 구할수 있습니다.

ii) 고르지 않는경우

d[i+1][j]=d[i][j]이 되나, 고려해주지 않아도 결과엔 지장을 주지 못합니다.

왜냐하면 d[i+1][j]에서 정답이 나오는 경우, d[i][j]에서도 정답이 나와 비용인 j를 구하는데 지장이 없기 때문입니다.

초항은

d[0][0번째 원소의 비용]=0번째 원소의 메모리

으로 두고,

반복문을 이용해 계산했습니다.

이중 주어진 M을 넘는 d[i][j]중 j의 최솟값을 구하면 답을 구할수 있습니다.

어디가 잘못된걸까요?