문제 풀이/백준
[S3] 백준 21921 - 블로그 (Python3)
gnoJJ
2023. 1. 14. 18:21
https://www.acmicpc.net/problem/21921
21921번: 블로그
첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다
www.acmicpc.net
해결방법
구간 합 중 가장 큰 값이 무엇이며, 그 값이 몇 번 나오는지 파악해야 하는 문제로 누적합과 슬라이딩 윈도우를 이용할 줄 알아야 한다.코드
N, X = map(int, input().split())
arr = list(map(int, input().split()))
prefix = [0]
for i in range(N):
prefix.append(prefix[i] + arr[i])
left = 0
right = X
ans = 0
period = 0
while right <= N:
partSum = prefix[right] - prefix[left]
if ans == partSum:
period += 1
elif ans < partSum:
period = 1
ans = partSum
right += 1
left += 1
print(f"{ans}\n{period}" if ans > 0 else "SAD")코드 설명
누적합을 담아둘 리스트는 prefix라는 변수에 담는다.left, right는 prefix의 인덱싱을 할 인덱스이다.ans와 period는 출력하려는 답이다.
prefix의 기간(right와 left의 차) 만큼 방문한 수를 계산함으로써 ans, period를 구한다.
