[Python] 백준 21921 블로그

1. 문제 링크

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

21921번: 블로그

 

2. 문제 요약

X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는가

 

3. 아이디어 정리

1. 누적합을 먼저 구한다.
2. 슬라이딩 윈도우로 특정 기간 동안 최대 값인 경우 방문자 수와 기간을 갱신한다.

 

4. 문제 풀이

4-1. 내 풀이

n, x = map(int, input().split())  # 블로그 일수, x일 동안 가장 많이 들어온 방문자
arr = list(map(int, input().split()))

if max(arr) == 0:
    print("SAD")
else:
    # prefix 만들기
    prefix = [0]
    for i, a in enumerate(arr):
        prefix.append(prefix[i] + a)

    left = 0
    right = x
    result = 0
    count = 0

    while right <= n:
        if right - left == x:
            if result < prefix[right] - prefix[left]:
                result = prefix[right] - prefix[left]
                count = 1
            elif result == prefix[right] - prefix[left]:
                count += 1
            left += 1
            right += 1

    print(result)
    print(count)

 

 

5. 결론

• 슬라이딩 윈도우로 해결