[백준][21921번] 블로그

문제

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

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

 

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

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

입력

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

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

출력

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

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

 

 

 

 

내 생각

 

Input)

5 2

1 4 2 5 1

Ouput)

7

1

 

문제 요약

1. 1일차부터 N일차까지 주어지고, X일 동안의 방문자가 궁금하다.

2. X일 동안 가장 많은 방문자 수와 가장 많이 방문한 기간이 몇번인지 출력하라

3. 만약 최대 방문자 수가 0명이라면 SAD를 출력하라

 

떠오른건 누적합이지만, 일단 그냥 풀어봤다. 풀고보니 슬라이딩 윈도우 !

이전 구간에서 더한 요소 빼고, 새로운 요소 추가하고를 반복해서 비교해준다. 

간단했지만 왜 오래 걸렸는지 ~~~~,

빨리 푸는 연습이 필요하닥 휴

 

+ 누적합으로도 마저 풀어봤다.

누적합은 미리 처음부터 끝까지의 누적합을 배열에 저장하고, 그 배열을 이용해서 구간합을 구했다.

 

 

 

 

내 코드

1. 슬라이딩 윈도우 

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

# 만약 방문자 수가 모두 0인 경우 SAD를 출력
if(max(visit)) == 0:
    print("SAD")

else:
	# 처음 X일 동안의 방문자 수의 합
    total = sum(visit[:X])
    # 최대 부분합
    max_total = total
    # 최대 부분합을 가지는 횟수
    cnt = 1

	#X일 이후 나머지 구간에 대해 반복
    for i in range(X, N):
    	#현재 방문자 수 합 계산
        total += visit[i]
        # 이전 X일 빼줌 (그러면 현재만 남게됨)
        total -= visit[i-X]

        if(total > max_total):
            max_total = total
            cnt = 1
        elif (total == max_total):
            cnt += 1

    print(max_total)
    print(cnt)

 

2. 누적합

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

if(max(visit)) == 0:
    print("SAD")

else:
    #누적합 배열
    arr = [0] * (N+1)
    for i in range(1, N+1):
        arr[i] = arr[i-1] + visit[i-1]

    max_total = 0
    cnt = 0

    for i in range(X, N+1):
        total = arr[i] - arr[i-X]
        if(total > max_total):
            max_total = total
            cnt = 1
        elif (total == max_total):
            cnt += 1

    print(max_total)
    print(cnt)