2559번: 수열

📋 문제 정보

문제 출처: https://www.acmicpc.net/problem/2559
문제 유형: 누적합
소요 시간: 30분

문제 요약

길이가 K인 구간의 합 중 가장 큰 값을 출력

🤔 아이디어

핵심 알고리즘

7개의 숫자가 있을 때 구간의 크기가 5인 경우 구간은 다음과 같다.

1, 2, 3, 4, 5
2, 3, 4, 5, 6
3, 4, 5, 6, 7

이때 볼드체로 표시된 부분의 계산의 중복을 누적합으로 개선할 수 있다.

의사 코드

# 누적합: sums[i] = nums[0] + ... + nums[i]
sums = [0] * (n + 1)
nums = [0] + nums # index 패딩

# 누적합 계산
for idx in range(1, n + 1):
	sums[idx] = sums[idx - 1] + nums[idx]

# 모든 구간 중 가장 큰 값 구하기
for start in 구간이 가능한 곳:
	# start부터 k개의 구간합: sums[start + k - 1] - sums[start - 1]

시간 복잡도

누적합 계산: $O(n)$
가장 큰 구간 계산: $O(n)$

최종 시간 복잡도: $O(n)$

🖨️ 입출력 분석

시간 복잡도 분석

수열의 원소 개수가 최대 10만개이므로 $O(nlogn)$이하의 알고리즘 사용

유의사항

k = 3이고 구간의 시작은 start이면 구간의 끝은 start + 3 - 1이다. start + 3이 아니다.

추가 테스트 케이스

5 3
1 2 3 4 5
-> 12

💭 생각 정리

누적합을 구할 때 앞에 0을 패딩하는 이유

누적합의 정의는 다음과 같다.

sums[i] = nums[0] + ... + nums[i]

누적합으로 구간합을 구하려면 다음과 같다.

section(start, end) = sums[end] - sums[start - 1]

이때, sums를 0부터 시작하면 sums[0 - 1] = sums[-1]이 발생한다.

이러한 상황을 쉽게 처리하기 위해 앞에 0을 하나 패딩한다.

구간이 가능한 곳의 범위

1번째 수부터 n번째 수는 range(1, n + 1)로 표현할 수 있다.

이때, k개의 원소를 가질 수 있는 start의 범위는 range(1, n + 1 - (k - 1))이 된다.

range(1, n + 1 - k)는 start로부터 k개 떨어진 곳들의 모음을 나타내므로 다르다.

📄 소스 코드

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
nums = list(map(int, input().split()))

def solution(n, k, nums):
    nums = [0] + nums
    sums = [0 for _ in range(n + 1)]

    # 누적합 구하기
    for idx in range(1, n + 1):
        sums[idx] = sums[idx - 1] + nums[idx]

    # 모든 구간 중 가장 큰 값 구하기
		answer = float("-inf")
    for idx in range(1, n + 1 - (k - 1)):
        result = sums[idx + k - 1] - sums[idx - 1]
        answer = max(result, answer)

    return answer

print(solution(n, k, nums))