2559번: 수열
https://www.acmicpc.net/problem/2559
문제 정의
어떤 정수의 수열이 주어졌을 때, 연속적인 며칠 동안의 숫자의 합이 가장 큰 값이 무엇인지 알아보는 문제이다.
접근 방법
- Naive 한 방법
- 온도 리스트를 순회하면서 K만큼 해당하는 부분 리스트의 합을 구한다. → 최대 이다.
- 그 합들 중에서 가장 큰 부분 합을 리턴한다. 최대 O(N) 이다.
- 따라서 시간 초과 발생하므로, 누적합을 이용해 효율적으로 풀 수 있다.
- 누적합을 이용한 방법
- 온도 리스트를 순회하면서 누적합을 구해서 prefix_sum 리스트에 저장한다.
- K만큼 해당하는 구간 리스트의 합은 누적합의 성질을 이용해서 구할 수 있는데,
예를 들어 (5, 6, 7, 8)의 합을 구하고 싶다면,
prefix_sum[8] - prefix_sum[4]를 계산하면 된다.
문제 해설
누적합 리스트인 prefix_sum을 순회하면서 각 인덱스에서 K의 차이마다 계산한 값 중 가장 큰 값을 리턴한다.
풀이
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
temper = list(map(int, input().split())) # 온도 리스트
prefix_sum = [0] * (N+1) # 누적합 리스트
sum = 0
# 누적합 만들기
for i in range(N):
sum += temper[i]
prefix_sum[i+1] = sum
max_value = -1e9
for i in range(0, N-K+1):
result = prefix_sum[i+K] - prefix_sum[i]
max_value = max(max_value, result)
print(max_value)
정리
- 처음에 prefix_sum의 개수를 temper와 동일하게 맞추려다 보니 맨 처음 시작의 누적합을 포함할 수 없었다. 그래서 prefix_sum의 개수를 (N+1) 으로 재 초기화 해서 다시 풀었다.
- 또한 for문의 인덱스를 처음 N-K로 했다가, 마지막까지 계산하지 않는 것을 깨닫고 N-K+1로 변경해주었다.
- 누적합을 구할 때 인덱스는 더욱 중요한 것 같다.
Uploaded by N2T
