[백준 1660번] 캡틴 이다솜 (C++)

문제링크 : https://www.acmicpc.net/problem/1660

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N;
int arr[121], dp[300001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    for(int i=1; i<121; i++) //30만이 넘기 시작하는 값
    {
        arr[i] = i*(i+1)*(i+2) / 6; //사면체 대포알 수 구하는 공식
    }

    cin >> N;
    for(int i=1; i<300001; i++) dp[i]=i; //사면체 없을 시 i개 사용

    for(int i=1; i<121; i++)
    {
        for(int j=arr[i]; j<=N; j++)
        {
            dp[j] = min(dp[j], dp[j-arr[i]] + 1); //사면체 대체
        }
    }

    cout << dp[N];

    return 0;
}

 

먼저 사면체 대포알 수 구하는 공식을 이용하여 미리 사면체 대포알 갯수를 구해준다.

이때 문제의 대포알 최대 갯수가 30만인데, 이에 맞게 가능한 최대 i 값인 120까지 구하도록 하였다.

 

이후 dp 배열을 초기화 해주는데 사면체를 생각하지 않고 단순히 대포알 그대로 사용한다 했을 때 입력받은 값 그대로 필요하므로 i개로 초기화를 진행해준다.

 

이제 미리 구했던 사면체에 해당하는 값을 토대로 해당 사면체가 존재하면 사면체로 대체를 하여 dp식을 갱신한다.