백준 1660번 캡틴 이다솜

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

문제풀이

사용한 알고리즘 : DP

(1) 코드 6~8

 'triangle[k] = 사이즈 k의 사면체 만들 때 필요한 대포알 수'라고 설정하였습니다. 

 N이 최대 3*10^5 으로 주어지므로, 배열 크기는 넉넉히 200 정도로 했습니다. 

(2) 코드 31~34

 과정(1)에서 만들어 놓은 사면체를 만들 때 필요한 대포알 개수를 구해줍니다.

 i번째에서 추가되는 대포알 수는 1+2+...+i = i*(i+1)/2 인 것을 생각해줍니다.

(3) 코드 8~10

 'dp[x] : x개의 대포알로 만드는 최소 사면체 수' 라고 설정하였습니다.

(4) 코드 12~27

 임의의 수 x가 주어졌을 때, x개의 대포알로 만드는 최소 사면체 수를 구하는 함수입니다.

 주어진 x크기로 만들 수 있는 k사이즈의 사면체를 각각 만들어 보면서,

 구하고자 하는 x개의 대포알로 만드는 최소 사면체 수를 구하고, 이를 dp로 저장합니다.