[백준 21921번] 블로그

문제 링크 >> https://www.acmicpc.net/problem/21921

 

 

📋 문제

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

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

 

 

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

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

 

 

👉 입력

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

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

 

 

👈출력

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

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

 

 

📝 풀이

import sys
input = sys.stdin.readline

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

temp = sum(arr[:x])
result = temp
day = 1

for p in range(x, n):
  temp += arr[p] - arr[p - x]
  if temp == result:
    day += 1
  elif temp > result:
    result = temp
    day = 1

if result == 0:
  print("SAD")
else:
  print(result, day, sep='\n')

 

슬라이딩 윈도우를 사용한 풀이이다.

슬라이딩 윈도우를 사용하지 않으면 시간초과가 난다.

 

먼저 1일차부터 x-1일차까지의 방문자 수 합을 구해 temp에 저장한다.

이후 n까지의 값을 확인하면서 x일 동안의 방문자 수 합을 구한다.

이때 계산 횟수를 줄이기 위해 이전 방문자 수 합에서 빼야 할 일자의 방문자 수를 빼고 더해야 할 일자의 방문자 수를 더하는 식으로 x일 동안의 방문자 수를 구한다.

 

방문자 수 합을 살펴보며 새로 큰 값이 나왔을 때는 최댓값을 갱신시켜준다.