백준21921 문제 보러가기

문제

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

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

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

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

입력

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

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

출력

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

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

제한

$1 \le X \le N \le 250,000$ 

$0 \le$ 방문자 수 $\le 8,000$ 

예제 입력 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

문제 해결 과정

문제는 간단했다.
주어진 X가 옮겨 다닐(?) 배열의 크기였고 그거를 처음부터 움직이면 된다.
나는 그래서 처음에 슬라이싱을 사용해서 움직이려고 했다.

그래서 내가 처음에 짠 코드는 다음과 같았다.

N, X = map(int, input().split())

people = list(map(int, input().split()))
s = 0
cnt = 1
for i in range(N-X+1) :
    l = sum(people[i:i+X])
    if s < l :
        s = l
        cnt = 1
    elif s == l :
        cnt += 1
if s == 0 :
    print('SAD')
else :  
    print(s)
    print(cnt)

그런데 이렇게 하니 시간초과가 떴다.
아마 sum 함수 내의 슬라이싱이 for문을 돌 때마다 계산되어서 그런 거 같다.
그러면 for문을 돌 때마다 값을 더하는 것이 아니라 가장 나중에 더해진 것을 빼고 가장 최근에 더해진 것을 더해야한다.

예를 들어, [1, 4, 2, 5, 1]의 배열이 있다고 하고 X가 2면 먼저 1부터 변수 하나에 더한다. 그 다음에는 4가 더해진다. 그러면 5가 된다. 그다음은 1을 빼고, 다음 값인 2를 더한다. 그러면 6이 된다. 이러한 식으로 큰 값을 찾아가면 최대값을 구할 수 있다.

최종 코드

N, X = map(int, input().split())

people = list(map(int, input().split()))

value = sum(people[:X])
s = value
cnt = 1

for i in range(X, N) :
    value += people[i]
    value -= people[i-X]
    
    if value > s :
        s = value
        cnt = 1
    elif value == s :
        cnt += 1
        
if s == 0 :
    print('SAD')
else :  
    print(s)
    print(cnt)