BOJ16238

독수리

k개의 양을 골라보면 항상 도망가지 않게 먹을 방법이 존재한다. 또한 그 값은 k개 수의 합 - (0+1+...+k-1)이다.

k개를 먹을 때 - (0+1+...+k-1)은 일정하므로, 선택하는 k개의 수를 최대화 하면 최대이다.

따라서 내림차순으로 정렬해서 a[i]-i가 음수가 아닐때까지 계속 선택해주는 그리디가 가능하다.

home