백준 27923 햄버거최대 몇개드실수있나요?

문제 정보

문제링크
햄버거의 질량을 줄여주는 콜라의 효과 지속 시간과 배치도가 제공되었을 때, 햄버거의 순서를 바꿔서 햄버거의 질량을 최소한으로 만들었을 때의 값을 구하는 문제이다.

배경 지식

콜라의 지속시간이 있으므로 콜라 하나 당 여러 개의 햄버거에 영향을 끼칠 수 있는 구조이다. 지속시간 동안 for문을 돌면서 업데이트를 시킬 수도 있겠지만, 그렇게 될 경우 최악의 경우에 (콜라의 개수가 20만이고, 지속시간이 20만이며, 모든 콜라를 첫 번째에 마실 경우) 한 개의 콜라에 20만씩, 콜라의 영향을 계산하는 데에만 4000억번의 연산을 해야할 수도 있다. 따라서 이런 영역 계산을 줄여주기 위해서 사용하는 알고리즘이 차분배열 또는 imos 알고리즘이다.

imos (Indexed Modification of Sums)법

• 특정 구간을 빠르게 업데이트하고, 이를 통해 누적합을 구할 때 유용한 알고리즘
• 핵심은 업데이트 구간을 배열에 기록 후, 누적 합을 통해 최종 값을 계산

즉 아까 말한 최악의 케이스의 경우 0번 인덱스에 콜라가 사용되었고, 20만1번째에 콜라 사용량을 -1을 한다고만 기록하는 것이다. 20만의 연산이 2번으로 줄었다. 이렇게 양이 늘어날 경우와 줄어드는 타이밍만 기록해서 나중에 한번에 몰아서 업데이트 하는 방식이다. 차분배열이라고도 한다. imos는 1차원 배열 뿐만 아니라 n차원 배열에서도 사용 가능한데, 다른 문제를 풀면서 다시 한 번 연습해볼 예정.

구현

# 햄버거의 개수, 햄버거의 질량, 콜라의 지속시간
n, k, l = map(int, input().split())
# 햄버거의 질량 리스트. 나중의 계산을 위해 미리 정렬한다.
h = sorted(map(int, input().split()))

# 효과를 기록해둘 차분배열 e
e = [0]*n
for i in map(int, input().split()):
    e[i-1]+=1
    if i+l <= n:
        e[i+l-1] -= 1

for i in range(1,n):
    e[i] += e[i-1]

# 콜라 효과가 가장 적을 때에 가장 작은 햄버거를 먹을 수 있도록 정렬해서 확인한다.
e.sort()

# e[j]가 30 이상일 경우 분모가 분자의 최대값보다 더 커지므로 신경쓰지 않아도 된다.
# 2^30 = 1,073,741,824 > 10^9
result = sum(h[j] >> e[j] for j in range(n) if e[j] <30)
print(result)

결과

와! 62명 중이긴 하지만 1등!