Codeforces Round #748 (Div. 3)-C. Save More Mice

문제 설명

고양이 한마리와 쥐 $k$마리가 있다. 그리고 수직선에 구멍 하나가 있다. 고양이는 $0$번 지점에 위치해있고 구멍은 $n$번 지점에 위치해있다. 모든 쥐는 고양이와 구멍 사이에 위치해 있다. $i$번째 쥐는 $x_i(0<x_i<n)$ 번 지점에 위치해 있다. 각 지점에는 여러 쥐가 같이 있을 수 있다.

1초에 다음 일이 일어난다. 먼저 오직 1마리의 쥐만 오른쪽으로 $1$만큼 이동한다. 만약 쥐가 구멍에 도달하면 숨는다.(쥐는 더이상 움직이지 않고 고양이한테 잡아먹히지 않는다.) 그 다음(쥐의 움직임이 끝난다음) 고양이가 오른쪽으로 $1$ 만큼 이동한다. 만약 고양이의 위치에 쥐가 여러마리 있으면 고양이는 이들을 다 잡아먹는다. (쥐는 더 이상 움직이지 못한다.) 이 행동은 고양이가 구멍에 도착할 때 까지 계속된다.

다시 말해서 첫번째는 쥐가 움직이고 만약 쥐가 구멍에 도달하면 생존한다. 그리고 고양이가 움직이는데 고양이는 쥐가 있는 위치에 도착하면 쥐를 잡아먹는다. (만약 고양이가 구멍에 도착하면 아무도 먹지 못한다.)

각 초마다 당신은 쥐를 선택해서 $1$칸 움직에게 할 수 있다. 고양이하게 먹히기 전에 구할 수 있는 쥐의 최대 개수는 무엇일까?

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t(1\le t\le {10}^4)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 숫자 $n$과 $k(2\le n\le {10}^9,1\le k\le 4\cdot {10}^5)$ 가 주어진다.

각 테스트케이스의 두번째 줄에는 쥐의 초기 위치인 $k$개 정수 $x_1,x_2,....,x_k(1\le x_i<n)$ 이 주어진다.

Output
각 테스트케이스마다 고양이에게 먹히기 전에 구멍에 도달 할 수 있는 쥐의 최대개수 $m$을 출력한다.

Example
input
3
10 6
8 7 5 4 9 4
2 8
1 1 1 1 1 1 1 1
12 11
1 2 3 4 5 6 7 8 9 10 11

output
3
1
4

문제 접근

사용한 알고리즘: 그리디 알고리즘
걸린 시간 : 00:06
생각보다 문제 접근 방법이 바로 떠올라서 쉽게 풀었다. 백준에서 비슷한 문제를 푼 것 같기도 한게 내가 알고리즘 공부를 허투루 한게 아니라는 생각이 들어서 내심 뿌듯했다.

일단 문제를 다 읽으면 구멍이랑 가장 가까운 쥐 부터 순차적으로 이동하는 것이 최적의 해답이라는 것을 몇번 예시를 들어서 구성해보면 알 수 있다. 쥐 한마리가 이동해야 하는 거리는 $n-x_i$이다. 그리고 고양이가 이동해야하는 거리는 $n$이다. 그러면 고양이가 $n$만큼 이동할때 까지 구멍에 가장 가까운 쥐부터 차례대로 이동해서 넣으면 되지 않을까?

구멍에 가장 가까운 쥐의 거리부터 시작해서 계속 쥐가 이동해야 하는 거리를 더하다가 그 값이 고양이가 이동해야 하는 거리와 같거나 크면 그 쥐를 포함해서 이후는 살 수가 없다. 즉 구멍에 가까운 거리부터 차례대로 누적합을 구하는데 누적합이 고양이가 이동해야 하는 거리보다 작으면 그 쥐는 고양이가 도착하기전에 반드시 살 수 있다. 이 사실은 조금만 생각하고 예시를 노트에 그려보면 알 수 있다. 그리고 이런 유형의 문제는 생각보다 많이 나와서 알아두면 반드시 도움이 될 것이다.

정답 코드

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

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n, k; cin >> n >> k;
        int arr[k];
        for(int i = 0; i < k; i++) cin >> arr[i];
        sort(arr, arr + k, greater<int>());
        int sum = 0, ans = 0;
        for(int i = 0; i < k; i++){
            sum += n - arr[i];
            if(sum >= n) break;
            ans++;
        }
        cout << ans << "\n";
    }
}