[python] 백준 10025번 - 게으른 백곰

10025번: 게으른 백곰 (acmicpc.net)

10025번: 게으른 백곰

우선

ㅠㅠ

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
arr = dict()

for i in range(n):
    a , b = map(int,input().split())
    arr[b] = a

ans = []
start = k
temp = 0
while start != max(arr.keys()) - k + 1:
    start += 1
    for i in arr.keys():
        if i in range(start - k , start + k + 1):
           temp += arr[i]
        else:
            ans.append(temp)
            temp = 0
print(max(ans))

시간초과 나온 코드임니덩

---

결국 구글링 하구 왔슴니당

[백준 10025] 게으른 백곰 ( 투 포인터 및 부분 합 ) (tistory.com)

[백준 10025] 게으른 백곰 ( 투 포인터 및 부분 합 )

 이분 코드 보면서

감탄 계속 하면서 봤그등요,,,

그 얼음 합 구하는 법 완전 상상 초월이었어요

일단 코드 이분꺼 다 베꼈슴니다

 

일ㄹㄹ단 오늘 배운 점

arr.sort(key=lambda b: b[0])

이게 b를 기준으로 sort 한다는 건데

2차원? 다차원? 배열일때 이런 식으로 오름차순 하나봐요

 

result = 0
start = 0
end = 0
while start <= end and end < n:
    s, _ = arr[start]
    e, _ = arr[end]
    if e - s <= 2 * k:
        sum = prefix_sum[end] - prefix_sum[start] + arr[start][1]
        result = max(result, sum)
        end += 1
    else:
        start += 1

end에서 start 뺀 값으로 k * 2 범위 안에 들어가나 비교하는 게

아..! 싶었슴니다

range에 틀에박힌 사고 벗어낫슴니다 ㅠ

prefix_sum = [0]
for x,g in arr:
    prefix_sum.append(prefix_sum[-1]+g)
prefix_sum = prefix_sum[1:]

이것도 대박인게

1 2 3 4 5

가 얼음 먹을 수 있는 개수라고 칠 때

1+2, 1+2+3, ... , 1+2+3+4+5

를 배열에 넣어놓고

start end에 따라서

(1+2+3+4)  -  (1+2) 이런 식으로 해서 3 + 4 나올 수 있게

미리 배열에 구해서 넣어놓는건데

-1 인덱스에 계속 더해서 한다는 부분이랑

저 위에 써놓은 방식 진짜 감탄 고자체였슴니당

이 문제 상당히 레죤두네용 하기 잘했슴니당

레죤두