[BOJ] 사격 - Compy's Blog

사격

TimeLimit	MemoryLimit	Condition	TAG
1s	1024MB	(1<=N, M, Sᵢ <= 10⁵,1<=A<=10¹⁰)	binary search

성현이네 부대의 24-1분기 사격 훈련이 시작되었다! 성현이네 부대의 사격 훈련장에는 $N$개의 표적이 있으며, 그중 $i$번째 표적의 점수는 $s_i$이다. 점수가 $s_i$인 표적을 맞히기 위해선 사격 실력이 최소 $s_i$ 이상이어야 한다. 만약 해당 표적을 성공적으로 맞혔다면, 표적의 점수만큼 사격 점수를 획득하며 사격 실력도 동일한 만큼 증가한다. 이번 사격 훈련에서는 최대 $M$번 사격할 수 있으며, 성현이가 진급에 성공하기 위해서는 획득한 사격 점수의 총합이 $A$점 이상이어야 한다. 사격 훈련을 시작하기 전 초기 사격 점수는 $0$점이다. 성현이는 항상 자신이 맞힐 수 있는 표적 중 얻을 수 있는 사격 점수가 가장 높은 표적을 맞히며, 동일한 표적을 여러 번 맞히는 것도 가능하다. 진급이 절실했던 성현이는 사격 훈련이 시작하기 전 초기 사격 실력이 어느 정도여야 진급에 성공할 수 있을지 궁금해하고 있다. 성현이를 위해, 진급에 성공하기 위한 초기 사격 실력의 최솟값을 구해주자. 항상 진급에 성공할 수 있는 경우만 입력으로 주어진다.

우리는 문제를 보는 순간 아! 라고 외치지 않을까 한다.

느므느므 큰 범위를 보고, 값을 찾는 문제여서 바로 이분탐색으로 접근하였다.

(나중에 더욱 자세히 쓸 예정…)

정답 코드

#define MAX 2'100'000'000
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <random>
using namespace std;

using ull = unsigned long long;
using ll = long long;
int score[100001];
ull n, m, a;
bool visited[100001];
bool debug_ = false;
ull current_ = 0;
ull binary_search_(ull current, int depth){
    if(depth >= m|| current >= a) return current;
    int left = 0, right = n-1;
    current += current_;
    int val = -1;

    while(left < right ){
        int pivot = (left+ right) / 2;
        if(score[pivot] < current){
            if(pivot+1 < n && score[pivot+1] > current){
                val = score[pivot];
                break;
            }
            left = pivot+1;
            
            if(left < 0 || score[left] > current) continue;
            val = max(val, score[left]);
        }
        else if(score[pivot] > current){
            right = pivot - 1;
            if(right < 0|| score[right] > current) continue;
            val = max(val, score[right]);
        }
        else {val = score[pivot]; break;}

    }


    if(val == -1) val = score[left];
    if(val > current) return 0;
    current-=current_;
    ull result = binary_search_(current + val, depth+1);
    return result;
}

int main(){
    
    cin >> n >> m >> a;
    int limit = 0;
    for(int i = 0; i < n; i++){ cin >> score[i]; limit = max(limit, score[i]);}
    sort(score, score+n);
    if(n == 1){
        cout << score[0];
        return 0;
    }
    
    int left = 1, right = limit;
    ull result = MAX;
    while(left <= right){
        current_ = (left + right) / 2;
        ull tmp = binary_search_(0, 0);
        if(tmp >= a){
            result = min(current_, result);
            right = current_-1;
        }else{
            left = current_+1;
        }
    }
    cout << result;
    return 0;
}