21921. 블로그

문제

백준 21921번 블로그

---

풀이

언젠가 배웠었던 슬라이딩 윈도우가 생각났다.
그래놓고 처음엔 for문에서 sum() 함수 돌렸다. 시간초과 날 줄도 모르고 ㅎ;

n, x = map(int, sys.stdin.readline().split())
visited = list(map(int, sys.stdin.readline().split()))

s, cnt = 0, 0
for i in range(0, n-x+1):
    if sum(visited[i:i+x]) > s:
        s = sum(visited[i:i+x])
        cnt = 1
    elif sum(visited[i:i+x]) == s:
        cnt += 1
print(f"{s}\n{cnt}") if s else print("SAD")

아니나다를까 시간초과를 맛보고 포인터를 썼다.

최대값을 저장할 M을 새로 선언하고 포인터로 l, r을 사용했다.

n, x = map(int, sys.stdin.readline().split())
visited = list(map(int, sys.stdin.readline().split()))

l, r = 0, x
s = sum(visited[l:r])
M, cnt = s, 1
while r < n:
    s += visited[r] - visited[l]
    if M < s: M, cnt = s, 1
    elif M == s: cnt += 1
    l += 1
    r += 1
print(f"{M}\n{cnt}") if M else print("SAD")

---

부족한 점

슬라이딩 윈도우로 처리될 때는 포인터를 사용해서 시간복잡도를 개선하자.