10025 게으른 백곰

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

N,K = map(int,read().split())
g_x = []
max_x = 0
for _ in range(N):
    g,x = map(int,read().split())
    max_x = max(max_x,x)
    g_x.append([g,x])

ice_array = [0 for _ in range(max_x+1)]

for g,x in g_x :
    ice_array[x]=g

"""
곰이 좌우로 K만큼 떨어져 있는 얼음들을 긁어모을 수 있다.
"""
loc = 0
left = loc - K
if left < 0 :
    left = 0
right = loc + K
now_val = sum(ice_array[left:right+1])
max_val = now_val
while right < max_x:
    # 이제 곰이 한칸 움직이자.
    loc += 1
    # 좌우의 위치도 변화하면서 무게를 추가햇다 뺐다가 하자.
    left = loc - K
    if left <= 0 :
        left = 0
    else : # left는 처음엔 좀 특별하다. left가 1이상일 경우에 left-1의 위치에 있는 것을 빼주기 시작하자.
        now_val -= ice_array[left-1]

    right = loc + K
    now_val += ice_array[right]
    max_val = max(max_val,now_val)

print(max_val)

3. 풀이 및 생각

문제 풀이

이 문제의 핵심은 ice array를 만드는 것이라고 본다. 그 이유는, 슬라이딩 윈도우를 하기에 아주 적합한 형식으로 문제를 바꿔주기 때문이다. 그 외에는 한칸씩 이동하면서 left-1 을 빼주고 right를 더해주는 식으로 문제를 해결해나가자.

나의 생각

슬라이딩 윈도우 문제는 ice array처럼 배열이 생성되어 있어야 쉽게 풀 수 있는 것 같다.