단일 공격 직후에 광역 공격을 사용한다면, 두 공격의 순서를 바꾸어도 다른 몬스터가 받는 피해는 같다. 순서를 바꾼 뒤 단일 공격의 대상이 이미 처치되었다면 그 단일 공격은 생략할 수 있다. 따라서 광역 공격을 모두 먼저 사용하고, 남은 몬스터를 단일 공격으로 처치하는 최적의 방법이 존재한다.
광역 공격을 번 사용하면 체력이 이하인 몬스터가 모두 처치된다. 따라서 필요한 공격 횟수는 다음과 같다.
가 보다 크고 어떤 몬스터의 초기 체력과도 같지 않다면, 를 줄여도 남는 몬스터의 수가 같다. 그러므로 또는 인 경우만 확인하면 된다.
체력을 오름차순으로 정렬하여 이라 하자. 일 때의 공격 횟수 을 초기 정답으로 둔다. 각 서로 다른 체력의 마지막 위치 에 대해 를 계산하여 정답을 갱신한다. 시간 복잡도는 , 공간 복잡도는 이다.
또한 정답은 단일 공격만 사용하는 경우의 횟수인 이하이므로, 만 확인해도 된다. 체력이 이하인 몬스터의 수를 체력별로 세어 두면 시간에도 풀 수 있다.
Solution written by GPT6