적을 죽이는 무기로 최소 이동을 찾는 C++ 코드

n개의 요소가 있는 배열 A가 있고 또 다른 숫자 H가 있다고 가정합니다. H는 적의 체력입니다. 우리는 n개의 무기를 가지고 있고 i번째 무기의 공격력은 A[i]입니다. 다른 무기를 사용하여 적을 죽일 수 있습니다. 같은 무기를 연속으로 두 번 사용할 수 없습니다. 무기를 사용하여 적을 죽일 수 있는 최소 횟수를 계산해야 합니다.

따라서 입력이 A =[2, 1, 7]과 같으면; H =11이면 출력은 3이 됩니다. 왜냐하면 우리가 공격력이 7인 무기를 사용하면 2를 사용하고 다시 7을 사용하면 적을 죽일 수 있기 때문입니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

sort the array A
n := size of A
x := (A[n - 1] + A[n - 2])
return H / x * 2 + (H mod x + A[n - 1] - 1) / A[n-1]

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int H){
   sort(A.begin(), A.end());
   int n = A.size();
   int x = (A[n - 1] + A[n - 2]);
   return H / x * 2 + (H % x + A[n - 1] - 1) / A[n - 1];
}
int main(){
   vector<int> A = { 2, 1, 7 };
   int H = 11;
   cout << solve(A, H) << endl;
}

입력

{ 2, 1, 7 }, 11

출력

3