백준 1660. 캡틴 이다솜

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

1660번: 캡틴 이다솜

mark[i] = 1

우선 i개의 대포알로 하나의 사면체를 만들수 있다면 기록해놓는다. 

그리고 mark[i]가 1인 경우, 즉 i개의 대포알로 하나의 사면체를 만들수 있는 i를 vector에 저장해 놓는다. 

 

d[i]=j 가 i개의 대포알로 만들수 있는 최소 사면채의 갯수는 j라고 하자. 

i를 1부터 증가시켜가며 최소 값을 찾아가면 된다. 

 

최소값을 찾을때는 우선 i개의 대포알로 하나의 사면체를 만들수 있는지 확인한다. mark[i] 가 1인지. 

i 에서 벡터의 요소값을 뺀 값을 j라고 하면, d[j] +1 과 d[i]를 비교해서 최솟값을 구하면 된다.

d[j]+1인 이유는 벡터의 요소 값들은 x개의 대포알로 1개의 사면체를 만들수 있는 대포알갯수들 이기 때문이다.