백준 31264번 사격 Java

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

문제

---

생각하기

---

• 이분탐색 문제이다.
  

• 문제 제대로 이해못해서 삽질함;;

  • 쏠 수 있는 점수 중 최대값만 항상 쏜다는 점.

  • 같은 표적을 여러번 쏠 수 있다는 점

  • 사격 실력과 사격 점수는 다르다는 점

    - 사격 실력은 점수가 처음부터 설정하고 가지만, 점수는 0점으로 시작해야 함

    꼭 인지하기

• 문제 잘 읽기..

동작

결과

코드

---

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M, A;
    private static int[] arr;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        Arrays.sort(arr);
        sb.append(binarySearch());
        return sb.toString();
    } // End of solve()

    private static long binarySearch() {
        int low = 1;
        int high = arr[N - 1];
        long ans = Long.MAX_VALUE;

        if (arr[0] >= A) {
            return A;
        }

        while (low <= high) {
            int mid = (low + high) / 2;
            boolean ret = check(mid);

            if (ret) {
                ans = Math.min(ans, mid);
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return ans;
    } // End of binarySearch()

    private static boolean check(int firstPower) {
        if (arr[0] > firstPower) return false;

        int count = 0;
        long scoreSum = 0;
        long nowPower = firstPower;
        int nowIdx = 0;
        while (count < M) {

            boolean flag = true;
            for (int i = nowIdx; i < N; i++) {
                if (nowPower < arr[i]) {
                    nowIdx = i - 1;
                    flag = false;
                    break;
                }
            }

            if (flag) {
                if (arr[N - 1] <= nowPower) {
                    nowIdx = N - 1;
                }
            }

            nowPower += arr[nowIdx];
            scoreSum += arr[nowIdx];
            count++;
            if (scoreSum >= A) {
                return true;
            }
        }

        return false;
    } // End of check()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        A = Integer.parseInt(st.nextToken());

        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    } // End of input()
} // End of Main class