https://school.programmers.co.kr/learn/courses/30/lessons/142085
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
n
명을 가지고 있습니다.enemy[i]
마리의 적이 등장합니다.enemy[i]
명 만큼 소모하여 enemy[i]
마리의 적을 막을 수 있습니다.무적권
이라는 스킬이 있으며, 무적권
을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.무적권
은 최대 k
번 사용할 수 있습니다.준호는 무적권
을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 n
, 사용 가능한 무적권의 횟수 k
, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy
가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.
n
≤ 1,000,000,000k
≤ 500,000enemy
길이 ≤ 1,000,000enemy[i]
≤ 1,000,000enemy[i]
에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.enemy[i]
의 길이를 return 해주세요.n | k | enemy | result |
---|---|---|---|
7 | 3 | [4, 2, 4, 5, 3, 3, 1] | 5 |
2 | 4 | [3, 3, 3, 3] | 4 |
입출력 예#1
입출력 예#2
const check = (n, k, enemy, mid) => {
if (mid <= k) return true;
const list = enemy.slice(0, mid).sort((a, b) => b - a);
let sum = 0;
for (let i = k; i < list.length; i++) {
sum += list[i];
if (sum > n) return false;
}
return true;
};
function solution(n, k, enemy) {
let left = 0;
let right = enemy.length;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (check(n, k, enemy, mid)) left = mid + 1;
else right = mid - 1;
}
return left - 1;
}