[백준] 21921 블로그 / 구현 / Python 실3

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

 

슬라이딩 윈도우로 푸는 문제!

 

처음에는 for문 돌면서 배열에 s = a[i:i+k] 값을 저장하고, max 값을 업데이트 하는 방식으로 구현했는ㄴ데

이렇게 하면 O(n*x)가 되어 시간초과가 났다

 

그래서 슬라이딩 윈도우를 사용하면서

 

전역변수에서 현재 a[i]값을 더하고 이전 a[i-x] 원소 값을 빼서

현재 sum이 x개의 원소 합으로 유지되도록 구현한다

이렇게 하면 slicing으로 탐색해서 끊지 않아도 된다

 

만약 현재 sum이 이전 max값보다 크다면

count값을 1로 리셋하고

max값을 현재 sum으로 대체한다

 

만약 현재 sum과 max값이 같다면 count을 1 증가한다

 

max값이 0보다 크면 max값과 count값을 출력하고

그 외에는 SAD를 출력한다

 

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


a = list(map(int,input().split()))
cur = sum(a[:x])
ma= cur
cnt=1
for i in range(x,n):
    cur+=a[i]-a[i-x]
    if cur>ma:
        cnt=1
        ma=cur
    elif cur==ma:
        cnt+=1
if ma>0:
    print(ma)
    print(cnt)
else:
    print("SAD")