DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

짐비의 사냥

Back to problem

Editorial

단일 공격 직후에 광역 공격을 사용한다면, 두 공격의 순서를 바꾸어도 다른 몬스터가 받는 피해는 같다. 순서를 바꾼 뒤 단일 공격의 대상이 이미 처치되었다면 그 단일 공격은 생략할 수 있다. 따라서 광역 공격을 모두 먼저 사용하고, 남은 몬스터를 단일 공격으로 처치하는 최적의 방법이 존재한다.

광역 공격을 KKK번 사용하면 체력이 KKK 이하인 몬스터가 모두 처치된다. 따라서 필요한 공격 횟수는 다음과 같다.

f(K)=K+∣{i∣1≤i≤N, Hi>K}∣.f(K)=K+\left|\{i\mid 1\leq i\leq N,\ H_i>K\}\right|.f(K)=K+∣{i∣1≤i≤N, Hi​>K}∣.

KKK가 000보다 크고 어떤 몬스터의 초기 체력과도 같지 않다면, KKK를 111 줄여도 남는 몬스터의 수가 같다. 그러므로 K=0K=0K=0 또는 K=HiK=H_i인 경우만 확인하면 된다.

체력을 오름차순으로 정렬하여 A1≤A2≤⋯≤ANA_1\leq A_2\leq\cdots\leq A_NA1​≤A2​≤⋯≤A이라 하자. 일 때의 공격 횟수 을 초기 정답으로 둔다. 각 서로 다른 체력의 마지막 위치 에 대해 를 계산하여 정답을 갱신한다. 시간 복잡도는 , 공간 복잡도는 이다.

또한 정답은 단일 공격만 사용하는 경우의 횟수인 NNN 이하이므로, 0≤K≤N0\leq K\leq N0≤K≤N만 확인해도 된다. 체력이 NNN 이하인 몬스터의 수를 체력별로 세어 두면 O(N)O(N)O(N) 시간에도 풀 수 있다.

Solution written by GPT6

K
=
Hi​
N
​
K=0K=0K=0
NNN
iii
Ai+N−iA_i+N-iAi​+N−i
O(Nlog⁡N)O(N\log N)O(NlogN)
O(N)O(N)O(N)