[Python] 백준 21921번 - 블로그

📖 문제

21921번: 블로그

 

🔎 풀이

슬라이딩 윈도우를 활용하는 문제입니다. 먼저 주어진 기간인 X 크기의 윈도우를 생성합니다. 이후 윈도우를 한 칸씩 오른쪽으로 이동하면서 각 윈도우의 합을 계산해줍니다. 매번 sum 함수로 계산시 시간비용이 O(n)이므로, 이전 합에서 맨 앞의 원소를 빼주고, 새로 추가되는 원소를 더해주는 식으로 계산합니다. 

 

💻 코드

N, X = map(int, input().split())
# 방문자 수를 담는 리스트
visited = [int(x) for x in input().split()]
ans = []
# 슬라이딩 윈도우
i, j = 0, X
# 현시점 방문자 수 합계
cur = sum(visited[:j])
ans.append(cur)

while j < N:
    # 방문자 수 갱신
    cur = cur - visited[i] + visited[j]
    # 각 윈도우의 방문자 합계 저장
    ans.append(cur)
    # 슬라이딩 윈도우 이동
    i += 1
    j += 1

max_visited = max(ans)
if not max_visited:
    print("SAD")
else:
    print(max_visited)
    print(ans.count(max_visited))