n개의 요소를 가진 배열 A와 하나의 숫자 H가 주어졌다고 가정해 봅시다. 여기서 H는 적의 체력(HP)입니다. 우리는 n개의 무기를 보유하고 있으며, i번째 무기의 공격력은 A[i]입니다. 서로 다른 무기를 조합하여 적을 처치할 수 있지만, 같은 무기를 연속으로 두 번 사용할 수 없다는 제약 조건이 있습니다. 목표는 적을 처치하기 위해 무기를 사용해야 하는 최소 사용 횟수를 구하는 것입니다.
예를 들어 입력이 A = [2, 1, 7], H = 11이라면 출력은 3이 됩니다. 공격력 7인 무기 → 공격력 2인 무기 → 다시 공격력 7인 무기 순으로 사용하면 총 데미지 16으로 적을 처치할 수 있기 때문입니다.
접근 방법
이 문제를 해결하는 핵심 아이디어는 다음과 같습니다.
같은 무기를 연속해서 사용할 수 없으므로, 가장 강한 무기와 두 번째로 강한 무기를 번갈아 가며 사용하는 것이 항상 최적의 전략입니다. 따라서 배열을 정렬한 뒤, 상위 두 무기의 공격력 합을 한 사이클의 데미지로 계산하면 됩니다.
알고리즘 단계
배열 A를 오름차순으로 정렬 n := A의 크기 x := (A[n - 1] + A[n - 2]) // 가장 강한 두 무기의 공격력 합 return H / x * 2 + (H mod x + A[n - 1] - 1) / A[n-1]
동작 원리:
- H / x * 2 : 가장 강한 두 무기를 번갈아 사용하는 완전한 사이클의 횟수 × 2 (각 사이클마다 두 번의 공격)
- (H % x + A[n - 1] - 1) / A[n - 1] : 남은 체력을 처리하는 데 필요한 추가 공격 횟수 (올림 나눗셈)
C++ 구현 예제
아래 구현을 통해 더 잘 이해해 보겠습니다.
#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
시간 복잡도
배열 정렬에 O(n log n), 이후 계산은 O(1)이므로 전체 시간 복잡도는 O(n log n)입니다. 정렬 대신 최댓값과 두 번째 최댓값만 한 번의 순회로 찾으면 O(n)으로 최적화할 수도 있습니다.