[S3] 백준 21921 - 블로그 (Python3)

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

21921번: 블로그

 

---

해결방법

구간 합 중 가장 큰 값이 무엇이며, 그 값이 몇 번 나오는지 파악해야 하는 문제로 누적합과 슬라이딩 윈도우를 이용할 줄 알아야 한다.

---

코드

N, X = map(int, input().split())
arr = list(map(int, input().split()))

prefix = [0]
for i in range(N):
    prefix.append(prefix[i] + arr[i])

left = 0
right = X

ans = 0
period = 0

while right <= N:
    partSum = prefix[right] - prefix[left]

    if ans == partSum:
        period += 1
    elif ans < partSum:
        period = 1
        ans = partSum

    right += 1
    left += 1

print(f"{ans}\n{period}" if ans > 0 else "SAD")

코드 설명

누적합을 담아둘 리스트는 prefix라는 변수에 담는다.left, right는 prefix의 인덱싱을 할 인덱스이다.ans와 period는 출력하려는 답이다.

 

prefix의 기간(right와 left의 차) 만큼 방문한 수를 계산함으로써 ans, period를 구한다.

---