캡틴 이다솜
면접 대비시간 제한2초메모리 제한128 MB
대포알 N개를 모두 써서 사면체 수들의 합이 N이 되도록 하는 최소 사면체 개수를 동적 계획법으로 구합니다.
문제
캡틴 이다솜은 해적선에 적을 공격할 대포알을 많이 보관해 둔다. 미적 감각이 뛰어난 이다솜은 대포알을 반드시 사면체 모양으로 쌓아야 한다고 생각한다.
크기 N의 더미는 한 변의 길이가 N인 정삼각형 층을 바닥에 놓고, 그 위에 한 변의 길이가 N-1인 정삼각형 층을 올리는 방식으로 만든다. 이 과정을 반복해 마지막에는 한 변의 길이가 1인 정삼각형 층을 올린다.
크기가 3인 더미는 다음과 같다.
X
X
X X
X
X X
X X X
각 정삼각형 층에 들어가는 대포알 수는 1, 3, 6, 10, ...개이다. 따라서 완성된 사면체 하나에 들어가는 대포알 수는 1, 4, 10, 20, ...개이다.
현재 해적선에는 대포알이 N개 있다. 이다솜은 영식이에게 이 대포알로 사면체 더미들을 만들라고 했다. 영식이는 가능한 한 적은 수의 사면체를 만들려고 한다. N개의 대포알을 모두 사용해서 만들 수 있는 사면체 개수의 최솟값을 구하시오.
입력
첫째 줄에 자연수 N이 주어진다. N은 300,000보다 작거나 같다.
출력
첫째 줄에 N개의 대포알을 모두 사용해 만들 수 있는 사면체 개수의 최솟값을 출력한다.