[백준] 21921번 블로그(python)

문제)

알고리즘)

- 시간복잡도를 생각하지 않고 문제를 본다면 대부분 for문과 sum 함수를 반복해서 사용해서 코드를 짜면 될 것 같지만

예시)

for i in range(N-X+1):  #윈도우의 크기와 graph의 크기를 고려해서 움직일 수 있는 횟수만큼 반복
    now = sum(graph[i:i+X]) #매번 sum함수로 해당 윈도우안에 해당하는 값 sum 

이 경우 시간복잡도에서 걸리게 되어 시간초과가 됩니다.(for문과 sum 동시에 반복시 n^2의 시간복잡도 갖는다 최악!!)

 

- 핵심은 이름 그대로 Sliding Window처럼 지나가면서 윈도우에서 벗어나는 값은 빼고 새로 들어오는 값 더하기 

   start += graph[i] #들어오는 값    start -= graph[i-X]빠져나가는 값

코드)

#블로그
import sys
input = sys.stdin.readline

N, X = map(int, input().split()) #총일 윈도우 크기

graph = list(map(int, input().split())) #일별 방문자 수 리스트


if max(graph) == 0:# 전체가 0이여야 나오는 경우가 "SAD"
    print("SAD")

else:
    start = sum(graph[:X])#맨 처음 초기값만 sum함수 사용
    total = start
    cnt = 1 #최대합이 갯수는 0이 아닌 경우 모두 1
    for i in range(X, N):
        start += graph[i]
        start -= graph[i-X]

        if start > total:
            total = start
            cnt = 1

        elif start == total:
            cnt += 1



    print(total)
    print(cnt)