백준 23830 : 제기차기 (Python)

본문 링크

import sys
input=sys.stdin.readline


N=int(input())
L=list(map(int,input().split()))

P,Q,R,S=map(int,input().split())

start=1 ; end=20000000000

while start<=end:

    mid=(start+end)//2
    total=0

    for i in range(N):
        if L[i]>mid+R:
            total+=L[i]-P
        elif L[i]<mid:
            total+=L[i]+Q
        else:
            total+=L[i]
    if total>=S:
        end=mid-1
    else:
        start=mid+1

if start>=20000000000:
    print(-1)
else:
    print(start)

📌 문제를 어떻게 접근할 것인가?

제기차기 점수의 합이 $S$ 점 이상인지 확인하는 문제이다.
다만 어떤 학생의 제기차기 점수가 $K+r$ 초과라면 그 학생의 점수에서 $p$ 를 빼고
제기차기 점수이 $K$ 미만이라면 그 학생의 점수에 $q$ 를 더한다.

이때 $S$ 점을 넘는 $K$ 의 최소값을 구한다.

문제 조건을 보면 아래와 같다.

•  $1 \leq N \leq 100\, 000$ 
  $0 \leq A_i \leq 100\, 000$ ($1 \le i \le N$)
  $1 \leq p,q < 5\, 000$ 
  $p+q \leq r < 10\, 000$ 
  $1 \leq S \leq 2 \times 10^{10}$ 

학생의 수가 10만이하일뿐더러 $S$ 의 범위가 매우 크다. 모든경우의 수를 구하기에는 시간초과가 발생하므로 이분탐색을 통해 문제를 풀어보고자한다.

📌 이분탐색을 어떻게 적용시킬것인가?

우리가 구하고자 하는 값은 K의 최소값이다. 따라서 $K$ 를 mid 값으로 잡는다.
start=1 , end=20000000000 으로 잡는다.
이후 리스트의 모든 원소를 탐색해서 각 리스트 값이 $K+r$ 초과이면 $p$ 를 빼고
$K$ 미만이면 $q$ 를 더한다. 둘다 아니라면 total 변수에 리스트 값을 그냥 더해준다.

모든 학생의 점수가 담긴 total 값이 $S$ 보다 크거나 같으면 end 값을 감소시키고 그렇지 않으면 start 값을 증가시킨다.

우리가 구하고자 하는 값은 $K$의 최소값이기 때문에 start 를 출력한다.
만약 start 가 end 보다 크거나 같은경우는 -1 를 출력한다.

✅코드에서 주의해야할 점

• 학생의 점수가 $K+r$초과 or $K$ 미만이 아니라면 그냥 더해준다.
• start=1 , end=20000000000 으로 잡아준다.
• $K$의 최소값을 구하기 때문에 start 를 마지막에 출력한다.