[백준][Python] 21921번. 블로그 (실버3)

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율

1 초

512 MB

12995

5461

4463

41.286%

문제

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

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

https://upload.acmicpc.net/5f95a11c-b879-408b-b3be-dcaa915f36ab/-/preview/

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

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

입력

첫째 줄에 블로그를 시작하고 지난 일수 𝑁$N$와 𝑋$X$가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1$1$일차부터 𝑁$N$일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력

첫째 줄에 𝑋$X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

제한

• $1 \le X \le N \le 250,000$
• 1≤𝑋≤𝑁≤250,000
• $0 \le$ 방문자 수 $\le 8,000$≤8,000
• 0≤

예제 입력 1

5 2
1 4 2 5 1

예제 출력 1

7
1

예제 입력 2

7 5
1 1 1 1 1 5 1

예제 출력 2

9
2

예제 입력 3

5 3
0 0 0 0 0

예제 출력 3

SAD

출처

• 문제를 검수한 사람: melon940925, rhs0266
• 문제를 만든 사람: tony9402

알고리즘 분류

• 누적 합
• 슬라이딩 윈도우

문제 풀이

'''
백준 실버3
21921번 블로그
'''
import sys
input = sys.stdin.readline

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

max_visitors = 0
current_window_sum = sum(visitors[:x])
max_visitors = current_window_sum
max_periods = 1

for i in range(x, n):
    current_window_sum += visitors[i] - visitors[i - x]
    if current_window_sum > max_visitors:
        max_visitors = current_window_sum
        max_periods = 1
    elif current_window_sum == max_visitors:
        max_periods += 1

if max_visitors == 0:
    print("SAD")
else:
    print(max_visitors)
    print(max_periods)