캡틴 이다솜 (백준 1660)

안녕하세요. 오늘은 사면체를 많이 만들거예요.

문제

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

아이디어

정삼각형만드는데 필요한 대포알의 개수를 sum[i], 정사면체를 만드는데 필요한 대포알의 개수를 sum2[i]라고 하면 sum[i]=sum[i-1]+i, sum2[i]=sum2[i-1]+sum[i]라고 표현할 수 있습니다.
이때 제가 계산해본 결과 sum2[i]가 30만을 넘어가는 i의 최솟값은 121이였습니다. 그래서 배열은 적당히 200개정도 잡아주면 됩니다.

dp[i]를 i개의 대포알을 모두 사용해서 만들 수 있는 정사면체의 최솟값이라고 정의합시다.
그러면 dp[i]는 dp[i-sum2[j]]+1의 최솟값이 됩니다. 이때 i-sum2[j]가 0이상일때에만 정의됩니다.
N의 범위가 2000이하이므로 그냥 2중 반복문으로 풀어주면 됩니다.

소스코드

#include <iostream>
#define ll long long
using namespace std;

ll dp[303030] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll sum[222] = { 0 }, sum2[222] = { 0 }, i, j;
    for (i = 1;; i++)
    {
        sum[i] = sum[i - 1] + i;
        sum2[i] = sum2[i - 1] + sum[i];
        if (sum2[i] > 300000) break;
    }
    ll MAX = i, N;

    cin >> N;
    for (i = 1; i <= N; i++)
    {
        dp[i] = 2e9;
        for (j = 1;; j++)
        {
            if (sum2[j] > i) break;
            dp[i] = min(dp[i], dp[i - sum2[j]] + 1);
        }
    }
    cout << dp[N];
}

감사합니다.