1660번: 캡틴 이다솜

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


$O(n^{4\over3})$

dp[n]: n개로 만드는 사면체 최소 개수

dp[0]=0
dp[n]=min(i*(i+1)*(i+2)/6<=n)(dp[n-i*(i+1)*(i+2)/6]+1)

#include<cstdio>
int n, dp[300001];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        dp[i] = 1e9;
        for (int j = 1, t; (t = j*(j + 1)*(j + 2) / 6) <= i; j++) if (dp[i - t] + 1 < dp[i]) dp[i] = dp[i - t] + 1;
    }
    printf("%d", dp[n]);
    return 0;
}