Codeforces Round #746 (Div. 2)-A. Gamer Hemose

문제 설명

핫산은 블리자드의 최신 망한 게임 발로란트를 즐기고 있다. 발로란트에는 $n$개의 무기가 주어지고, $i$번재 무기의 데미지 값은 $a_i$로 주어진다. 그리고 핫산이 무찔러야 하는 적의 체력은 $H$로 주어진다.

핫산은 적이 죽을 때 까지 한번 혹은 여러번 행동을 취할 수 있다.

한번의 행동에서 핫산은 무기를 1개 선택할 수 있고, 무기의 공격력으로 적의 체력을 깎을 수 있다. 적은 적의 체력이 0이거나 0보다 작아지면 죽는다. 그러나 세상은 간단하지 않다. 핫산은 같은 무기를 연속으로 2회 선택할 수가 없다.

핫산이 적을 죽이기 위해서 무기를 선택해야하는 최소 횟수는 무엇일까?

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^5)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 각 각 고를 수 있는 무기 개수와 적의 체력을 나타내는 두 정수 $n$과 $H (2 \le n \le 10^3, 1 \le H \le 10^9)$ 가 주어진다.

두번째 줄에는 각 무기의 공격력을 나타내는 $n$개 정수 $a_1, a_2, ..., a_n(1 \le a_i \le 10^9)$ 가 주어진다.

Output
각 테스트케이스마다 핫산이 적을 죽이기 위해서 무기를 선택해야하는 최소 횟수를 나타내는 정수 1개를 출력한다.

Example
input
3
2 4
3 7
2 6
4 2
3 11
2 1 7

output
1
2
3

문제 접근

사용한 알고리즘: 수학, 그리디 알고리즘, 정렬
걸린 시간 : 00:06
그리디 알고리즘이라는 건 알았지만 어떻게 푸는지 알았는데 삽질을 제대로 한 문제이다. 이 문제를 장장 1시간 만에 겨우 풀고 나는 퍼포먼스를 최초로 600대를 받았다는 웃지못한 소식이 전해지기도 했다. 그냥 전형적인 코드포스식 경우의수 나눠서 출력문 3번 쓰면 되는데, 너무 얕봤다.

문제를 읽어보면 알고리즘 문제를 푼 사람이라면 일단 이 생각이 떠오를 것이라고 생각한다. "그냥 공격력 쎈 무기로 때리면 최소값 나오겠는데?" 이 생각이 맞다. 그리고 한 무기로 연속해서 때릴 수 없기 때문에 가장 센 무기와 그 다음으로 센 무기로 번갈아 가며 때리면 최소값을 찾을 수 있다. 그런데 여기서 내가 헤맨 부분은 이 번갈아 가며 때리는 과정에서 경우의 수를 나누지 못했던 부분이였다.

일단 두 무기로 번갈아 가며 때릴때는 3가지 경우가 나올 수 있다. 가장 센 무기의 공격력을 $a$, 두번째로 센 무기의 공격력을 $b$라고 하자. 이 일반화가 가능한 이유는 $n$은 최소 $2$이기 때문이다.

1. 두 무기로 번갈아 가며 때릴때 정확히 0이 남는 경우. 즉, $a$와 $b$로 번갈아 때렸고, 딱 $b$까지 때렸을 때 적의 체력이 정확히 0이 남는 경우다. 이 경우에는 H/(a + b) * 2가 답이다. 두 무기로 번갈아 때렸기 때문에 2를 곱해야하는점은 잊으면 안된다.
2. 두 무기로 번갈아 가며 때릴때 적의 체력이 $a$보다 작거나 같은 경우이다. 즉, $a$와 $b$로 번갈아 때렸고, 딱 $b$까지 때렸을 때 적의 체력이 정확히 $a$보다 작거나 같은 경우다. 이 경우에는 마지막에 $a$로 한번 더 때리면 되기 때문에 답은 $H/(a + b) * 2 + 1$ 이 답이다.
3. 두 무기로 번갈아 가며 때릴때 적의 체력이 $a$보다 큰 경우이다. 즉, $a$와 $b$로 번갈아 때렸고, 딱 $b$까지 때렸을 때 적의 체력이 정확히 $a$보다 큰 경우다. 이 경우에는 마지막에 $a$로 한번 더 때리면 안되고 거기에 추가로 $b$로 한번 더 때려야 한다. 따라서 답은 $H/(a + b) * 2 + 2$ 이 답이다.

이런 경우의 수 나누는거 진짜 코드포스에 자주 나오는 유형이다. 업솔빙 계속하면서 이와 비슷한 문제를 빨리푸는 연습을 해야한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int n, h; cin >> n >> h;
        int arr[n];
        for(int i = 0; i < n; i++) cin >> arr[i];
        sort(arr, arr + n);
        int a = arr[n - 1], b = arr[n - 2];
        if(h % (a + b) == 0) cout << h / (a + b) * 2;
        else if(h % (a + b) <= a) cout << h / (a + b) * 2 + 1;
        else cout << h / (a + b) * 2 + 2;
        cout << "\n";
    }
    return 0;
}