출처 : 프로그래머스 디펜스 게임
난이도 : Level 2
문제
준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.
- 준호는 처음에 병사 n명을 가지고 있습니다.
- 매 라운드마다 enemy[i]마리의 적이 등장합니다.
- 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
- 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
- 무적권은 최대 k번 사용할 수 있습니다.
준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.
준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 1 ≤ n ≤ 1,000,000,000
- 1 ≤ k ≤ 500,000
- 1 ≤ enemy의 길이 ≤ 1,000,000
- 1 ≤ enemy[i] ≤ 1,000,000
- enemy[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 |
----------------------------------------------------------------------------------------------------------------------------
문제 해독
초기 병사, 스테이지 무적권, 라운드별 적 생성이 정해져 있고 가장 많은 스테이지를 클리어할 수 있는 최대 경우의 수를 구하는 문제
문제접근
각 라운드마다 병사를 소진하고 만약 완전 소진시 스테이지 무적권이 있다면 사용하고 소진된 병사를 다시 채워 다음 스테이지의 연산을 수행하여 가장 많은 스테이지를 클리어 시킵니다.
이때 이미 클리어한 스테이지의 병사의 수도 미리 확인을 해둔 상태로 병사 소진시 가장 많은 병사를 소진하였던 스테이지의 병사 수를 가져와서 채웁니다.
필요 변수 리스트
- 우선순위 큐
필요 알고리즘
- 그리디 알고리즘
- 우선순위 큐
- 순차 탐색
using System;
using System.Collections.Generic;
public class Solution {
public int solution(int n, int k, int[] enemy) {
int soldiers = n;
int pass = k;
MaxHeap maxHeap = new MaxHeap();
for(int i = 0; i < enemy.Length; i++) {
int e = enemy[i];
soldiers -= e;
maxHeap.Add(e);
if(soldiers < 0) {
if(pass > 0) {
int recover = maxHeap.PopMax(); // 소생 병사 가져오기(가장 많은 적군)
soldiers += recover;
pass--;
} else {
return i;
}
}
}
return enemy.Length;
}
}
// MaxHeap
public class MaxHeap {
private List<int> heap = new List<int>();
// 삽입
public void Add(int val) {
heap.Add(val);
int i = heap.Count - 1;
while(i > 0) {
int parent = (i - 1) / 2;
if(heap[parent] >= heap[i]) break;
Swap(i, parent);
i = parent;
}
}
// 반환
public int PopMax() {
int max = heap[0];
heap[0] = heap[heap.Count - 1];
heap.RemoveAt(heap.Count - 1);
int i = 0;
while(true) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if(left < heap.Count && heap[left] > heap[largest]) largest = left;
if(right < heap.Count && heap[right] > heap[largest]) largest = right;
if(largest == i) break;
Swap(i, largest);
i = largest;
}
return max;
}
private void Swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
