백준 21921번 - 블로그

블로그 문제 바로 가기

풀이 날짜: 2026-01-23

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline

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

current = sum(people[:x])
max_sum = current
count = 1

for i in range(x,n):
    current = current - people[i-x] + people[i]

    if current > max_sum:
        max_sum = current
        count = 1
    elif current == max_sum:
        count+=1

if max_sum == 0:
    print("SAD")
else:
    print(max_sum)
    print(count)
  

문제 접근

연속된 구간이 등장하는 순간, 모든 경우를 직접 나열하기보다는 구간을 이동시키는 방식을 떠올려야 한다. 특히 구간의 길이가 고정되어 있다는 점에서, 이 문제는 자연스럽게 슬라이딩 윈도우(Sliding Window) 유형으로 풀어야 했다.

슬라이딩 윈도우의 핵심

슬라이딩 윈도우의 핵심은 “앞의 값을 하나 빼고, 뒤의 값을 하나 더한다”는 것이다. 처음 구간의 합을 한 번만 계산한 뒤, 구간을 한 칸 오른쪽으로 이동할 때는 기존 합에서 왼쪽 끝 값을 빼고 새로 포함되는 값을 더해 주면 된다. 이 방식으로 모든 구간의 합을 O(n) 시간에 계산할 수 있다.

첫 번째 구간을 따로 계산하는 이유

슬라이딩 윈도우를 적용하기 위해서는 기준이 되는 첫 번째 구간이 필요하다. 그래서 배열의 앞에서부터 x개의 합을 먼저 계산해 초기값으로 사용한다. 이후부터는 이 값을 기준으로 구간을 이동시키며 합을 갱신한다. 이 초기 설정이 없으면 이후 갱신 로직이 성립하지 않는다.

최대 방문자 수와 횟수를 함께 관리해야 함

이 문제는 단순히 최대 합만 구하는 것이 아니라, 그 최대값이 몇 번 등장했는지도 함께 출력해야 한다. 따라서 구간 합이 최대값보다 크면 최대값을 갱신하면서 횟수를 1로 초기화하고, 구간 합이 최대값과 같으면 횟수를 증가시키는 식으로 관리해야 한다. 이 두 값을 동시에 관리하는 로직이 중요하다.