23829 인문예술탐사주간 (백준, python3)

23829번: 인문예술탐사주간

 

만약 태영이의 위치가 0이라면 사진의 점수는 모든 나무의 위치 총합이 된다.

태영이의 위치가 X일 때, X 오른쪽 나무들로 얻는 점수는 각 나무의 위치에서 X를 뺀 값의 총 합이 된다. X 왼쪽 나무들의 점수는 X에서 나무의 위치를 뺀 값의 총합이 된다. 결국 점수는 특정 위치로부터의 누적합이 되는 셈이다. i번째 나무까지의 누적합을 prepix[i]에 저장한다.

 

그림으로 보면 아래와 같다. 태영이가 13에 있다면 a와 b는 이렇게 그려볼 수 있다. 파란색이 빼야 하는 값들이다.

태영이의 왼쪽 나무들을 먼저 보자. 

태영이의 왼쪽 나무들의 수를 세서 태영이 위치에 곱한 다음 왼쪽 나무들의 누적합을 빼주면 왼쪽 나무의 점수다. 태영이의 위치를 X, 왼쪽 나무의 수가 left라면 이렇게 정리할 수 있다.

left_score = X*left - prepix[left]

여기서 태영이가 만약 모든 나무를 오른쪽에 두는 경우, left == 0, prepix[left] == 0 이어야 한다. 따라서 나무의 위치, 누적합은 0번 인덱스에 존재하지 않는 가상의 나무 0이 있다고 계산해야 한다.

 

태영이의 오른쪽 나무들은 더 쉽다.

전체 누적합에서 왼쪽 나무의 누적합을 빼면 오른쪽 나무들의 누적합을 얻을 수 있다. 여기서 태영이 위치에 오른쪽 나무들의 수를 곱해 빼면 된다. 오른쪽 나무의 수를 right라고 하면 이렇게 정리할 수 있다.

right_score = prepix[-1] - prepix[left] - X*right

태영이가 만약 모든 나무를 왼쪽에 두는 경우, prepix[-1] == prepix[left]이고, right == 0 이기 때문에 right_score == 0 이다.

 

이제 태영이가 왼쪽과 오른쪽에 나무를 각각 몇 그루 두고 있는지 찾아야 한다. 편의상 위치가 같거나 가장 가까운 왼쪽 나무의 번호를 찾는 것으로 태영이의 위치를 찾는다. 여기서는 이분탐색이 쓰인다. 최소 값보다 태영이의 위치가 작은 경우 제대로 탐색할 수 없으므로 가장 작은 값 0을 가상의 나무로 설정하고 탐색하도록 해야 한다.

태영이는 13에 있으므로 이분탐색 결과로 left == 3을 얻는다.

 

[정답코드]

N,Q = map(int,input().split())
P = [0] + sorted(list(map(int,input().split())))

def binsearch(t):
    s,e = 0,N
    while s < e:
        m = (s+e)//2
        if P[m] > t:
            e = m-1
        else:
            s = m
        if e-s == 1:
            P[e] > t:
                return s
            else:
                return e
    return s

prepix = [0]*(N+1)
for i in range(1, N+1):
    prepix[i] = prepix[i-1]+P[i]
    
for _ in range(Q):
    X = int(input())
    left = binsearch(X)
    right = N - left
    a = left*X - prepix[left]
    b = prepix[-1] - prepix[left] - right*X
    print(a+b)