[BOJ/백준] 23830 - 제기차기

 

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

 

 

 

---

이분탐색

+

K가 양의 정수, 즉 자연수를 말하고 0은 포함되지 않는다

---

---

• 제목

제기차기

---

• 조건

시간 제한 : 1 초

메모리 제한 : 512 MB

---

• 문제

얼마 전 학교 체육대회 "사차원"이 열렸다. 대회 종목 중 하나는 제기차기였고, 몇몇 학생을 제외하고는 대부분의 학생이 한두 번 밖에 차지 못했다. 잘 하는 사람과 못 하는 사람의 점수 차이가 너무 커졌기 때문에, 대회 전체 점수에 영향이 클 거라고 생각한 선생님은 다음과 같은 규칙을 정했다.

• 기준이 되는 양의 정수 K를 정한다.
• 어떤 학생의 제기차기 점수가 K+r 초과라면 그 학생의 점수에서 p를 뺀다.
• 어떤 학생의 제기차기 점수이 K 미만이라면 그 학생의 점수에 q를 더한다.

선생님은 이 규칙으로 점수를 계산한 후에, 전교생의 제기차기 점수 합이 S 미만이라면, 학생들에게 제기차기를 충분히 연습시키지 못한 태영이에게 체육관 청소를 시킬 예정이다. 선생님은 p, q, r, S를 정한 후에 태영이에게 K를 정해달라고 했다. 태영이가 청소를 하지 않아도 되도록 K를 정하는 방법이 있는지, 있다면 K로 가능한 최솟값은 얼마인지 구하여라.

---

• 입력

첫째 줄에 전교생 수 N이 주어진다.
둘째 줄에 학생 N 명의 제기차기 점수 A1, A2, ..., AN이 공백으로 구분되어 주어진다.
셋째 줄에 선생님이 정한 상수 p, q, r, S가 공백으로 구분되어 주어진다.

---

• 출력

태영이가 청소를 하지 않아도 되는 K의 최솟값을 출력한다. 만약에 어떻게 K를 정해도 태영이가 청소를 해야 한다면, -1을 출력한다.

---

예제 입력1	예제 출력1
5 3 6 10 1 12 1 2 3 34	4

예제 입력2	예제 출력2
3 2 6 8 1 4 6 29	-1

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        int[] score = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            score[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        int p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        long S = Long.parseLong(st.nextToken());

        int low = 1, high = 100_001, K = Integer.MAX_VALUE;
        while(low <= high){
            int mid = (low + high) / 2;
            long sum = 0;
            for (int i = 0; i < N; i++) {
                sum += score[i];
                if(mid + r < score[i]) {
                    sum -= p;
                } else if(score[i] < mid) {
                    sum += q;
                }
            }
            if(sum < S) {
                low = mid + 1;
            } else {
                K = Math.min(K, mid);
                high = mid - 1;
            }
        }
        System.out.println(K == Integer.MAX_VALUE ? -1 : K);
    }
}