BOJ 2295 세수의 합

자연수들로 이루어진 집합에서 적당히 세 수를 골라서(같은 수를 골라도 된다) 세 수의 합 d를 구했을 때 d가 그 집합의 원소가 되는 d 중에서 최대값을 구하는 문제이다.

일단, N제한이 1000이라 3가지 수를 고르는(같은 수도 포함) 방법의 수는 1000의 세제곱이 되어 다 해보는 것은 시간초과가 날 것이다.

문득 dp로 해보면 어떨까하는 생각이 들었다. d[val][n] = n개의 수를 더해서 val이 될 수 있는지 없는지. d[val][n]=d[val-a][n-1].. 이런 식으로... 근데 val이 최대 2억이라 메모리 초과이다.