[백준] 게으른 백곰

첫 접근

• 양동이가 놓일 수 있는 위치를 미리 0 으로 만든다.
• 양동이 위치를 하나씩 방문해, 해당 양동이부터 -K, +K 까지 범위에 얼음이 있는 양동이가 존재한다면, 양동이에 얼음을 합산한다.
• 최대 얼음이 존재하는 양동이의 인덱스 위치를 반환한다.

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

xg = {}
for _ in range(N):
    g, x = map(int, input().split())
    xg[x] = g
xg1 = dict(sorted(xg.items()))

mx = max(xg1)
mn = min(xg1)

length = mx - mn + 1
bag = [0 for _ in range(length)]

for i in range(mn, mx + 1):
    for j in range(i - K, i + K + 1):
        if j in xg1:
            bag[i - mn] += xg1[j]

print(bag.index(max(bag)) + 1)

결과

• 시간초과
• 비효율적인 탐색, 불필요한 반복

---

투포인터 알고리즘 or 슬라이딩 윈도우 기법

• 각 구간의 합을 한 번만 계산한다. 구간이 이동할 때마다 더하거나 빼는 방식으로 빠르게 구간 합을 업데이트할 수 있다.

참고한 솔루션

구간합 = 슬라이딩 윈도우

• 윈도우의 사이즈를 2*K + 1로 설정한다.
• 윈도우를 한 칸씩 옮겨가면서 마지막 값은 추가하고, 첫 번째 값은 빼주는 식으로 윈도우 값을 업데이트한다.

# 슬라이딩 윈도우
N, K = map(int, input().split())
ice = [0] * 10000001

for _ in range(N):
    g, x = map(int, input().split())
    ice[x] = g

# 초기 윈도우
window = sum(ice[:2*K+1])
max_sum = window

for i in range(1, 10000001 - 2*K):
    window = window - ice[i - 1] + ice[i + 2*K]
    max_sum = max(window, max_sum)
    
print(max_sum)

투포인터 익숙해지기.