[백준/누적합] 21921번 : 블로그

- 문제 : https://www.acmicpc.net/problem/21921

 

 

정답 풀이 

길이가 x인 구간의 원소합을 누적합으로 푸는 문제이다. (이중 반복문으로 풀면 시간복잡도가 올라갈 것 같다)

그런데 여기서 주의해야할 점이 2가지 있다. 

 

1. 누적합 계산식

일단 주어진 배열을 누적해서 더한 값을 num_sum이라는 배열에 저장한 뒤 반복문 돌면서 num_sum[i + x -1] - num_sum[i - 1] 계산식으로 각 구간의 합 중 최댓값을 answer에 저장하면된다. 

 

num_sum[i + x -1] - num_sum[i - 1]

 

여기서 헤맸던 부분이 위 계산식이다. i를 포함하고 길이가 x가 되려면 오른쪽 끝 인덱스는 i + x - 1이 되는 것 까지는 알았는데, 시작점이 i가 아니다. 누적합이라 i는 0인덱스부터 i인덱스까지의 합이므로 num_sum[i]를 빼는 것이 아니라, i 이전인 i - 1 값을 빼줘야 한다. 왜 그래야 하는지는 아래의 그림으로 쉽게 설명이 가능하다. 그래서 위의 계산식이 나온다.

 

2. 위 계산식으로는 엔드케이스(0부터 x - 1 까지)를 포함하지 못한다

누적합의 원리를 토대로 계산식은 구했지만 위 계산식으로는 i의 범위가 [1, n - x + 1]이 된다. 이렇게 진행하면 사실상 1부터 x 길이의 구간합을 구하는 것이라 0부터 x - 1까지의 누적합 계산을 하지 못한다. 그래서 num_sum과 arr 가장 왼쪽에 0을 추가해 엔드케이스까지도 포함해 계산할 수 있게 했다. 

arr = [0] + list(map(int, input().split()))

num_sum = [0] * (n + 1)
num_sum[1] = arr[1]
for i in range(2, n + 1):
    num_sum[i] = num_sum[i - 1] + arr[i]

 

 

n, x = map(int, input().split())
arr = [0] + list(map(int, input().split()))

num_sum = [0] * (n + 1)
num_sum[1] = arr[1]
for i in range(2, n + 1):
    num_sum[i] = num_sum[i - 1] + arr[i]


answer = 0
for i in range(n - x + 1):
    answer = max(answer, num_sum[i + x] - num_sum[i])


if answer == 0:
    print("SAD")
else:  
    count = 0
    for i in range(n - x + 1):
        result = num_sum[i + x] - num_sum[i]
        if result == answer:
            count += 1

    print(answer)
    print(count)