[백 준/구현] 2559: 수열

https://www.acmicpc.net/problem/2559

2559번: 수열

핵심 아이디어

• 구간 합 구하기

풀이

import sys
input = sys.stdin.readline

result =[]

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

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

sum 연산을 반복해서 계산을 하다 보니 시간 초과 문제가 생겼다. 그래서 sum을 한번만 연산하는 방식으로 풀이를 진행하였다. 처음에는 이 문제가 간단해 보였지만 고민을 해도 어떻게 풀어야할 지 떠오르지 않아 애를 많이 먹었던 문제다.

import sys
input = sys.stdin.readline

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

# 그 구간까지의 합을 저장하기 위한 빈 리스트
result = []
# 초기화
result.append(sum(data[:k]))

for i in range(n-k):
	result.append(result[i] - data[i] + data[i+k])

print(max(result))

주어진 리스트에서 연속된 k개의 요소의 합이 최대가 되는 구간을 찾는 알고리즘입니다. 주요 로직은 다음과 같습니다.

알고리즘 구현

• result = []: 연속된 k개 요소의 합을 저장할 리스트를 초기화합니다.
• result.append(sum(data[:k])): 처음 k개 요소의 합을 result 리스트에 추가합니다.
• 이후 for 루프에서는 현재 구간의 첫 번째 요소를 빼고, 다음 요소를 더하여 새로운 구간의 합을 구하는 방식입니다.
  • for i in range(n-k): n-k번 반복합니다. 
  • result.append(result[i] - data[i] + data[i+k]): 현재 구간의 첫 번째 요소(data[i])를 빼고, 구간 끝의 다음 요소(data[i+k])를 더해 새로운 구간의 합을 계산하고 result에 추가합니다.