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

https://www.acmicpc.net/problem/1660

1660번: 캡틴 이다솜

얼마 전에 풀었던 제곱수와 비슷한 느낌의 문제이다. 제곱수가 아닌 사면체의 대포알 개수로만 달라졌다. 사면체의 대포알 개수 배열을 만들어놓고 (한 125번째까지가면 300000보다 커진다) 나머지 알고리즘은 제곱수와 같다.

 

배열 dp에서 tri의 원소를 하나씩 빼가면서, 가장 작은 경우가 무엇일지 비교해주자.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int bullet;
	scanf("%d",&bullet);
	int tri[200]={}, cnt1=0, cnt2=0, cnt3=0;
	int dp[300001]={0,1,};
	for(int i=0; i<125; i++){
		cnt1++;
		cnt2+=cnt1;
		cnt3+=cnt2;
		tri[i]=cnt3;
	}
	for(int i=2; i<=bullet; i++){
		int j=0, Findmin=300001;
		while(i-tri[j]>=0){
			Findmin=min(Findmin, dp[i-tri[j]]+1);
			j++;
		}
		dp[i]=Findmin;
		
	}
	printf("%d",dp[bullet]);
}

---