백준 사격(31264)

 

이분 탐색 문제이다.

 

https://www.acmicpc.net/problem/31264

31264번: 사격

 

해당 문제를 정확이 풀기 위해서는 이분탐색을 사용해야한다.

 

처음에는 중복으로 사격 가능한걸 놓쳐서 고생을 하다 중복가능성을 보고 문제를 풀었다....

 

해당 문제는 현재 사격가능한 최대 점수 기준으로 최대 사격 점수를 가져와 나의 사격 가능 점수를 높이면서 M번 사격했을때 총합을 비교하면된다.

 

처음에는 위에 방법만 사용하니 50점을 맞았는데

 

최소 사격 점수를 순차로 진행을 시켰었는데 해당 방법을 이분탐색으로 변경하니 통과 했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * https://www.acmicpc.net/problem/31264
 */
public class Main {

    public static void main(String[] args) throws IOException {
        solution();
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int A = Integer.parseInt(st.nextToken());

        int[] score = new int[N];

        long max = Integer.MAX_VALUE;

        st = new StringTokenizer(br.readLine());
        for (int i=0; i < N;i ++) {
            score[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, score[i]);
        }

        Arrays.sort(score);

        long min = 1;

        while (min <= max) {

            long sum = 0;
            long mid = (min + max) / 2;

            for (int i=0; i < M; i++) {
                sum += getScore(score, mid + sum);
            }

            if (sum >= A) {
                max = mid - 1;
            } else if (sum < A){
                min = mid + 1;
            }

        }

        System.out.println(min);
    }

    public static long getScore(int[] score, long target) {

        long max_score = 0;
        int left = 0;
        int right = score.length - 1;

        while (left <= right) {

            int mid = (left + right) / 2;

            if (target >= score[mid]) {
                max_score = Math.max(max_score, score[mid]);
            }

            if (score[mid] > target) {
                right = mid - 1;
            } else if (score[mid] < target) {
                left = mid + 1;
            } else {
                break;
            }

        }

        return max_score;

    }
}

 

결과