[알고리즘] 백준 21921 파이썬 - 블로그

 

21921번: 블로그

문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

 

문제풀이

n,x = map(int,input().split())
arr=list(map(int,input().split()))
#01
if(max(arr)==0):
    print("SAD")
else:
	#02
    value = sum(arr[:x])
    max_value=value
    max_cnt=1
    #03
    for i in range(x,n):
    	#슬라이딩 윈도우
        value+=arr[i]
        value-=arr[i-x]
        #04
        if(value>max_value):
            max_value=value
            max_cnt=1
        elif value==max_value:
            max_cnt+=1
    print(max_value)
    print(max_cnt)

- 슬라이딩 윈도우 기법을 사용하였다.

- #01 : arr의 max값이 0이면 "SAD"를 출력해준다.

- #02 : value값에 arr을 0부터 x-1값까지의 합을 저장해준다.

           max_value에는 value값을 저장한다. max_cnt는 최솟값인 1로 지정한다.

- #03 : 슬라이딩 윈도우 기법을 통해 value에 arr[i]를 더하고 arr[i-x]를 뺸 

           즉 arr[0:2] -> arr[1:3] 이런식으로 값을 이동하며 전체를 탐색한다.

- #04 : 전체를 탐색하며 새로 만든 value값이 max_value보다 크면 그 값을 저장하고 cnt를 1로한다.

           value가 max_value와 같다면 cnt를 1 추가해준다.

- #05 : 최종적으로 나온 value와 cnt를 출력해준다.