[BOJ#21921] 블로그

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

1 초

512 MB

11714

4897

3995

41.109%

문제

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

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

 

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

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

입력

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

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

출력

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

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

제한

•  1≤X≤N≤250,000
•  0≤ 방문자 수 ≤8,000

---

제출 코드

# X일 동안 가장 많이 들어온 <방문자수, 기간>
# 블로그를 시작하고 지난 일수 N, X일 동안 가장 많이 들어옴
N, X = map(int, input().split())
arr = list(map(int, input().split()))
# X일 동안의 최대값을 구해야한다.
# 1. for문으로 전부 다 비교하면서 갱신?
# 2. dp 리스트를 만들어서 최대값만 반환? O(n)
dp = sum(arr[:X])

sumone = dp
cnt = 1
for i in range(1, N-X+1):
    dp = dp - arr[i-1] + arr[i+X-1]
    
    if sumone < dp:
        sumone = dp
        cnt = 1
    elif dp == sumone:
        cnt += 1

if dp == 0:
    print('SAD')
    exit()
else:
    print(sumone)
    print(cnt)

 

dp를 이용하여 최대값이 바뀔때마다 갱신해주고, 만약 같다면 갯수를 추가해 주는 방식으로 코드를 설계했다.

슬라이딩 윈도우라는 방식이라는데 이전 문제와 발상은 비슷하지만 값을 저장하는 방식이 달랐다.