[C++/1660] 캡틴 이다솜

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

정사면체가 하나씩 증가하는 공식과 그리고 그 크기만큼 정사면체를 만들 수 있다면? 그건 하나의 정사면체가 된다. 우리는 최소의 정사면체를 만들어야 하기 때문에, 최대한 정사면체를 크게 만들고 나머지 값으로 최소한의 정사면체를 만들어야하는 문제를 갖고 있습니다.

그래서 우리는 일단 개수따라 정사면체를 만들 수 있는지 알아야 한다. 그에 따른 공식은 아래의 코드와 같다. 그리고 이에 따라서 그 개수로 정사면체를 만들 수 있는 것이 된다.

아래는 점화식이다. 추후에 좀 더 자세히 작성을 해봐야 겠다.. 너무 피곤햇

일단 우리는 n개로 정사면체를 만들 수 있다는 것을 vector안에 차례로 추가해주었다.

그 값을 시작으로 ! 왜 이 값을 시작으로 할까? 이 값은 어쨌든 지금 당장 하나를 만들 수 있는 값이기 때문이다. 이어서 그 값을 시작으로 우리가 제시한 n개까지 어떻게 최소한의 값을 구할 수 있을까?

시작부터 차례대로, 시작값의 개수와 시작값에서 현재 크기를 제외한 값 + 1(이미 하나를 만들었기에, 현재 크기를 제외했기에) 그렇게 해서 최소값을 구하면 된다. 그렇다면 초기화로 1e9로 삽입해야겠다.

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

#define MAX 300001
using namespace std;

int n;
long long dp[MAX];
vector<int> v;

int main() {
	
	cin >> n;
	
	for(int i = 1; ; i++){
		int num = i * (i + 1) * (i + 2) / 6; // 50000
		if(num > MAX) break;
		v.push_back(num);
	}
	
	fill(dp, dp + MAX, 1e9);
	
	for(int i = 0; i < v.size(); i++){
		dp[v[i]] = 1;
	}
	
	for(int i = 0; i < v.size(); i++){
		for(int j = v[i]; j <= n; j++){
			dp[j] = min(dp[j], dp[j - v[i]] + 1);
		}
	}
	
	cout << dp[n];
	
	
	return 0;
}