백준 23978 : 급상승 (Python)

본문 링크

import sys
input=sys.stdin.readline


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

start=1 ; end=1000000000000000000

while start<=end:
    mid=(start+end)//2
    total = 0
    for i in range(1,N):
        if mid-(L[i]-L[i-1]-1)>=0:
            m = mid
            n=mid-(L[i]-L[i-1]-1)
            S=(n+m)*(m-n+1)//2
            total += S
        else:
            S=mid*(mid+1)//2
            total +=S
    total+=mid*(mid+1)//2
    if total>=K:
        end=mid-1
    else:
        start=mid+1

print(start)

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

먼저 예제입출력을 보자

• 입력
  3 10
  1 2 4

• 출력
  3

$X$ 가 3일때 3 3 2 3 2 1 0 으로 총 14원이 만들어진다.

이를 점화식을 만들어보면 수학공식을 통해
n부터 m까지의 합 S=(n+m) X (m-n+1)//2 과 1부터 n까지의 합 S= n X (n+1)//2 을 사용해서

m=$X$ , n=$X$ - ( L[i] - L[i-1] - 1) 이 되고
S= (n+m) X (m-n+1)//2 를 해주면 1부터 2까지의 수익 , 2부터 3,(4-1)일차까지의 수입을 O(1) 로 계산할수 있다.

예시로 $X$가 3이고 2일차부터 3,(4-1)일차까지의 합을 구하고자 하면
원래는 3 + 2 = 5가 된다.
점화식을 이용하면 m=3 , n=3-(4-2-1) = 2 가되고
3부터 2까지의 합이므로 S=(3+2) x (3-2+1)//2 = 5가 된다.

하지만 문제에서 주어지는 세 정수 $N$, $K$ , $A_i$ 의 범위가
(1 ≤ $N$ ≤ 10^6, 1 ≤ $K$ ≤ 10^18 , 1 ≤ $A_i$ ≤ 10^5) 로 매우 크다.
따라서 우리가 구하고자 하는 가장 작은 정수 $X$는 이분탐색을 통해 구해보고자 한다.

📌어떻게 이분탐색할 것인가?

먼저 start= 1 , end=10^18 으로 잡아주고 mid 값을 잡는다.
이후 모든 리스트 값에 대해서 아까 만든 점화식으로 L[i-1] 부터 L[i] 까지의 총 합을 구한후 total 변수에 그 값을 넣어준다. 이후 total 값이 $K$ 보다 크다면 end 를 감소시키고 그렇지 않다면 start 를 증가시킨다.

우리가 구하고자 하는 값은 $K$보다 큰 가장 작은 정수 $X$ 이므로 start 를 출력한다.

✅ 코드에서 주의해야 할점

• start = 1 , end=10^18 으로 잡는다
• 만약 mid 값이 L[i]-L[i-1]-1 미만이면 n 은 음수가 되므로 1부터 n까지의 합 공식을 사용한다.
• L[i-1] 일차부터 L[i]-1 일차 까지의 합을 구하였기 때문에 마지막 L[-1] 일차 또한 1부터 n까지 합 공식으로 구해줘야한다.
• $K$보다 큰 가장 작은 정수 $X$ 를 구하는 것이기 때문에 start 를 출력한다.