[백준] 21921 블로그

백준 21921번 블로그

투 포인터 / 누적 합 / 슬라이딩 윈도우

 

 

 

[문제]

 

 

 

구간 합 문제

접두사 합을 사용한 알고리즘을 적용하면 효과적

 

 

 

[과정]

 

1. 각 구간(data)에 대하여 누적 합을 계산한 배열(prefix_sum)을 생성
2. 0에서 부터 x만큼 증가하여 각 x기간 동안의 누적 합을 배열(result)에 저장
3. result중 최댓값을 출력하고, 해당 최댓값의 개수를 출력

 

 

 

[소스코드]

 

# 블로그

import sys
input = sys.stdin.readline

n,x = map(int, input().split())
data = list(map(int, input().split()))

sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

result = []

cnt = 0  
while cnt+x <= n:
    result.append(prefix_sum[cnt+x]-prefix_sum[cnt])
    cnt += 1
    
    
if max(result) == 0:
    print('SAD')
else:
    print(max(result))
    print(result.count(max(result)))

 

 

 

---

 

 

 

[통과]