1660 캡틴 이다솜

크기가 1인 구슬로 길이가 N인 정삼각형을 만들고, 위에 N-1, N-2... 1 의 정삼각형을 계속 쌓아서 사면체를 만드려고 한다. 구슬의 갯수를 주어주면 최소 몇개의 사면체를 만들 수 있는가를 출력하는 문제이다.

우선 사면체에 필요한 구슬의 갯수를 구해야 한다.
길이가 1씩 길어지면서 계속 쌓아야 하니, N은 1부터 시작해서 점차 증가하고 1~N의 합의 합을 구해야 한다. 그렇게 구한 각 사면체에 필요한 구슬 갯수들을 따로 배열로 저장해놓는다.

이제 만들수 있는 사면체 수의 최솟값을 구해야 하는데, 이것은 DP를 이용해야 한다.
해당 구슬의 갯수로 만들 수 있는 사면체 수를 비교하면서 작은 값으로 갱신해주면 된다.

소스