칼을 무기로 적을 물리치는 비디오 게임을 하고 있다고 가정해 보겠습니다. 주인공은 칼로 적을 직접 베거나(슬래시), 칼을 적에게 던질 수도 있습니다. 단, 던진 칼은 다시 회수할 수 없습니다. i번째 칼이 가하는 피해량은 배열 'knives'에 담겨 있으며, 각 요소는 {slash, throw} 형태입니다. 여기서 'slash'는 해당 칼로 적을 베었을 때의 피해량, 'throw'는 그 칼을 던졌을 때의 피해량을 의미합니다. 베기(slash)는 원하는 만큼 무제한으로 사용할 수 있지만, 각 칼은 딱 한 번만 던질 수 있습니다. 이제 체력이 h인 적이 등장했을 때, 이 적을 물리치기 위해 필요한 최소 작업 횟수(베기 또는 던지기)를 구해야 합니다. 적의 체력이 0이 되면 적은 쓰러집니다.
예를 들어 입력이 n = 2, h = 11, knives = {{4, 5}, {3, 6}}이라면 출력은 2가 됩니다.
주인공이 두 자루의 칼을 모두 던지면 가해지는 총 피해는 5 + 6 = 11입니다. 적의 체력이 0이 되어 적은 패배합니다.
접근 방법
이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다.
- 슬래시는 무제한으로 사용할 수 있으므로, 모든 칼 중에서 가장 큰 슬래시 피해량(val)을 미리 구해 둡니다.
- 어떤 칼의 던지기 피해량이 val보다 크다면, 그 칼을 한 번 던지는 것이 같은 칼로 반복해서 베는 것보다 유리합니다.
- 던지기로 처리하고 남은 체력은 가장 강한 슬래시로 반복해서 베어 마무리하며, 이때 필요한 횟수는 ceil(남은 체력 ÷ val)입니다.
단계
다음 절차에 따라 문제를 해결합니다.
val := 0
i := 0부터 시작하여 i < n 동안 i를 1씩 증가시키며 반복:
val := val과 knives[i].first 중 최댓값
배열 knives를 정렬
res := 0
i := 0부터 시작하여 i < n 동안 i를 1씩 증가시키며 반복:
만약 knives[i].second > val이라면:
h := h - knives[i].second
res := res + 1
만약 h <= 0이라면:
res 출력 후 종료
그렇지 않으면 반복문 탈출
(res + ceil(h / (double)val)) 출력
예시
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void solve(int n, int h, vector<pair<int, int>> knives){
int val = 0;
for(int i = 0; i < n; i++){
val = max(val, knives[i].first);
}
sort(knives.begin(), knives.end());
int res = 0;
for(int i = 0; i < n; i++){
if(knives[i].second > val){
h -= knives[i].second;
res++;
if(h <= 0){
cout << res << endl;
return;
}
}
else break;
}
cout << (res + ceil(h / (double)val)) << endl;
}
int main() {
int n = 2, h = 11;
vector<pair<int, int>> knives = {{4, 5}, {3, 6}};
solve(n, h, knives);
return 0;
}
입력
2, 11, {{4, 5}, {3, 6}}출력
2
위 코드는 먼저 최대 슬래시 피해량을 계산한 뒤, 던지기 피해량이 이보다 큰 칼들을 우선적으로 던져 체력을 깎습니다. 던지기만으로 적을 쓰러뜨리지 못했다면, 남은 체력을 최고 성능의 슬래시로 처리하는 데 필요한 횟수를 올림하여 더한 값을 결과로 출력합니다. 이처럼 그리디(greedy) 방식으로 각 단계마다 가장 효율적인 공격을 선택하면 최소 작업 횟수를 구할 수 있습니다.