⭐⭐2559: 수열

설명

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다.

 

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,

 

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

핵심 아이디어

해당 문제는 구간 합 중에서 가장 큰값을 출력하는 문제다. 구간 합을 구하는 문제는 보통 누적합을 활용해서 해결한다. 만약 sum 연산을 반복해서 계산하게 되면, 시간 초과 문제가 발생한다. 따라서 sum을 한번 만 연산하는 방식으로 풀어야 하는데, 처음 k개 요소의 합을 리스트에 넣어주고 계산하면 해결할 수 있다.

• for 루프에서는 현재 구간의 첫 번째 요소를 빼고, 다음 요소를 더하여 새로운 구간의 합을 구하는 방식입니다.

코드 구현

해당 풀이는 sum을 여러번 계산해서 시간 초과가 발생하는 풀이다.

import sys
input = sys.stdin.readline

ans = []
n,k = map(int, input().split())
a = list(map(int, input().split()))

for i in range(n-k+1): # 9
	ans.append(sum(a[i:i+k]))
print(max(ans))

 

다음 코드는 sum을 한번만 연산해서 시간 초과 문제를 해결한 풀이다. for 루프에서는 현재 구간의 첫 번째 요소를 빼고, 다음 요소를 더하여 새로운 구간의 합을 구하는 방식입니다. 그리고 첫번째 k요소의 합을 사전에 미리 구해놨기 때문에 반복문을 n-k번만 수행하게 된다.

import sys
input = sys.stdin.readline

ans = []
n,k = map(int, input().split())
data = list(map(int, input().split()))

# 연속된 k개 요소의 합을 저장할 리스트를 초기화
result = []
# 처음 k개 요소의 합을 리스트에 추가
result.append(sum(data[:k]))
# 반복문을 순회하면서 현재 구간의 첫 번째 요소를 제외하고,
# 다음 요소를 더하여 새로운 구간의 합을 구하는 방식이다.
for i in range(n-k): # 처음 k개ㅇ 요소의 합이 사전에 리스트에 추가했기 때문
	result.append(result[i] - data[i] + data[i+k])

print(max(result))