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

백준 실버3 10025번 게으른 백곰 - Python

https://www.acmicpc.net/problem/10025

10025번: 게으른 백곰

---

문제

맞았습니다가 뜬 코드입니다. - 메모리 66100KB | 시간 488ms | 코드 길이 390B

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
arr = [list(map(int, input().rstrip().split())) for _ in range(N)]
ice = [0]*(1000000+1)
for i in range(N):
    ice[arr[i][1]] = arr[i][0]
next = 2*K + 1
window = sum(ice[:next])
answer = window
for i in range(next, 1000001):
    window += (ice[i] - ice[i-next])
    answer = max(answer, window)
print(answer)

슬라이딩 윈도우 알고리즘을 이용한 방법입니다.

 

슬라이딩 윈도우 알고리즘이란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘을 말합니다. 예를 들면 다음 이미지와 같습니다.

---

Try1.

런타임에러(ValueError)가 뜬 코드입니다.

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
bucketList = [0]*1000000
xMax = 0
for i in range(N):
    g, x = map(int, input().rstrip().split())
    bucketList[x] = g
    if x > xMax:
        xMax = x
ice = list()
temp = 0
for i in range(1+K, xMax-K+1):
    for j in range(i-3, i+3+1):
        temp += bucketList[j]
    ice.append(temp)
    temp = 0
print(max(ice))

• x좌표가 0일때 오류가 발생하는 것을 발견했습니다.

---

Try2.

런타임에러(IndexError)가 뜬 코드입니다.

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
bucketList = [0]*(1000000+1)
xMax = 2*K+1
for i in range(N):
    g, x = map(int, input().rstrip().split())
    bucketList[x] = g
    if x > xMax:
        xMax = x
ice = list()
temp = 0
for i in range(K, xMax-K+1):
    for j in range(i-K, i+K+1):
        temp += bucketList[j]
    ice.append(temp)
    temp = 0
print(max(ice))

• x좌표가 1000000일때 오류가 발생하는 것을 발견했습니다.

---

Try3.

시간초과가 뜬 코드입니다.

import sys
input = sys.stdin.readline
N, K = map(int, input().rstrip().split())
bucketList = [0]*(1000000+1)
xMax = 0
xMin = 1000000
for i in range(N):
    g, x = map(int, input().rstrip().split())
    bucketList[x] = g
    if x > xMax:
        xMax = x
    if x < xMin:
        xMin = x
ice = list()
temp = 0
if xMin - K < 0:
    start = 0
else:
    start = xMin - K
if xMax + K > 1000000:
    end = 1000000
else:
    end = xMax + K
e = start + 2*K
while start <= end:
    if e >= end:
        e = end
    temp += sum(bucketList[start:e+1])
    ice.append(temp)
    temp = 0
    start += 1
    e += 1
print(max(ice))

---

Search 🔍

• 코드 참고 : https://whwl.tistory.com/232
• 슬라이딩 윈도우 설명 : https://ji-musclecode.tistory.com/37
• https://velog.io/@zwon/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window

---

후기

시간초과가 떴을 때 그냥 코드 찾아봤는데 카테고리 뭔지 한번 보고 슬라이딩 윈도우가 뭔지 먼저 찾았다면 좋았을 듯 싶습니다..

 

어제 오늘 1시 경에 미용실에 가려고 동네 미용실에 갔는데 아조시가 11시 오픈인데도 안 오셔서

그냥 집으로 와버렸어용. . .

 

덕분에 자를까 말까 고민하는 중