BOJ 10025번: 게으른 백곰

www.acmicpc.net/problem/10025

10025번: 게으른 백곰

아이디어:

부분합을 이용하면 되지 않을까. 2k+1만큼의 길이를 더하면서 최댓값을 갱신한다..

일단 ice배열을 1,000,000개씩 만들고, g와 x를 받으면서 ice[x]=g를 넣는다.

그리고 큐를 하나 만들어서 ice를 하나씩 추가하고 길이가 2k+1이 되면 하나씩 pop하고 다음 걸 더한다.

이때 최댓값을 갱신해준다.

 

간단한 문제인데.. 이렇게 막막하면 우짤꼬....ㅠㅠ

#게으른 백곰

import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
ice = [0] * (10**6+1)

max_x = 0 #x의 최댓값
for _ in range(n):
    g, x = map(int, sys.stdin.readline().split())
    ice[x] = g
    max_x = max(x, max_x)

q = deque()
ans = 0
temp = 0
for i in range(0, max_x+1):
    if (len(q)==2*k+1): #큐의 길이가 2k+1이면 원소를 하나 제거한다.
        temp -= q.popleft()
    temp += ice[i]
    q.append(ice[i])
    ans = max(ans, temp) #최댓값 갱신

print(ans)
    

    

좌표가 0부터인데 1부터로 설정해서 틀렸었다.

 

그리고 굳이 deque를 쓰지 않고 그냥 인덱스가 i>2*k인 경우에 temp에서 바로 제일 왼쪽의 ice값을 뺄 수 있다. 이를 위해서는 제일 왼쪽의 ice 인덱스를 저장하는 변수를 또 하나 만들어야 한다.

#게으른 백곰

import sys

n, k = map(int, sys.stdin.readline().split())
ice = [0]*(10**6+1)

max_x = 0 #x의 최댓값
for _ in range(n):
    g, x = map(int, sys.stdin.readline().split())
    ice[x] = g
    max_x = max(x, max_x)

ans = 0
temp = 0
left = 0
for i in range(0, max_x+1):
    if (i>2*k):
        temp -= ice[left]
        left+=1
    temp += ice[i]
    ans = max(ans, temp) #최댓값 갱신

print(ans)

난 이게 더 좋다.