[Python] 백준 21921 블로그 - 누적합(prefix sum) / 슬라이딩 윈도우

누적합(Prefix sum)이란?

: 말 그대로 누적된 합을 구하는 것이다.

arr = [1, 4, 6, 8, 4, 2]

예를 들면 배열이 위와 같이 주어진 경우

  arr[0]까지의 누적합은 1, arr[1]까지의 누적합은 1+4 = 5, … , arr[4]까지의 누적합은 1+4+6+8+4 = 23이 된다.

 

 

---

 

슬라이딩 윈도우란?

: 위 그림에서 파란색 네모로 묶은 것처럼 배열 내 특정 구간(구간에 포함될 숫자의 개수)을 지정한 후 그 수를 유지한 채 index를 하나씩 밀면서 수들의 합을 파악하는 것이다.

arr = list(map(int, sys.stdin.readline().split()))

x_sum = sum(arr[:X])        # X일까지의 방문자 수 누적 합
result = x_sum              # 처음 담아놓은 x_sum이 최대 합일 수 있기 때문
cnt = 0                     # 최대 방문자 수를 나타낼 수 있는 기간의 수

for i in range(X, N):

    x_sum += arr[i]         # 다음 인덱스 값 더하기
    x_sum -= arr[i-X]       # x_sum의 첫 인덱스 값 빼기

위 코드에서 for 문에 적은 것처럼

처음 지정한 x_sum안에 있는 제일 첫번째 인덱스 값을 x_sum에서 빼고, x_sum의 바로 뒤에 처음으로 오는 인덱스의 값을 더하는 방식으로 진행하면서 수들의 합을 파악할 수 있다.

 

 

---

오답 코드.py

# from sys import stdin as s
import sys
# s=open("input.txt", "rt")

N, X = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

x_sum = sum(arr[:X])        # X일까지의 방문자 수 누적 합
result = x_sum              # 처음 담아놓은 x_sum이 최대 합일 수 있기 때문
cnt = 0                     # 최대 방문자 수를 나타낼 수 있는 기간의 수

for i in range(X, N):
    x_sum += arr[i]         # 다음 인덱스 값 더하기
    x_sum -= arr[i-X]       # x_sum의 첫 인덱스 값 빼기

    if x_sum > result:      # x_sum이 누적합의 최대값
        result = x_sum      # result에 누적합의 최대값을 넣어줌
        cnt = 1
    elif result == sum:   # 슬라이딩 윈도우를 하면서 최대값을 발견하면 cnt에 +1을 해줌
        cnt += 1

if result == arr[0] + arr[1]:        # 첫번째 오답 1) arr배열의 첫번째 인덱스의 값과 두번째 인덱스 값의 합이 결국 x_sum이면 처음부터 +1을 해줘야 하므로
    cnt += 1

if result == 0:
    print("SAD")
else:
    print(result)
    print(cnt)

70% 근처에서 터지는데 주어진 예제도 다 올바른 값이 출력되고 질문게시판에 있는 반례들도 다 잘 출력되는데

왜 틀린지는 모르겠다. 해결 후 정답 코드 추가 예정

 

+ 다음날 아침에 씻으면서 갑자기 어느 부분 코드를 잘못 짰는지 생각났다..........

if result == arr[0] + arr[1]:
	cnt += 1

여기가 문제였다.

 

첫번째 예제 입력/출력 부분만 보고 반례를 잡다가 X=2일때를 한정해서 이 부분의 코드를 작성한 게 실수였다.