[백준] 2559 수열 (Python 파이썬)

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

2559번: 수열

문제 설명

그림과 함께 제공되는 문제이니 자세한 문제설명은 위 링크를 참조해주세요.

---

풀이 과정

이 문제는 누적 합 으로 푸는 문제이다.

누적합을 이용하지 않고 단순 합계를 이용한다면 시간초과 오류가 나게 된다.

 

한번 구간합을 구하는 시간복잡도는 O(n)이고 m번동안 수행을 하게 된다면

총 시간복잡도는 O(nm)이 되는데 데이터가 10만개가 되면 시간초과 오류가 나게 된다.

 

그래서 매번 구간합을 구하는 것이 아니라,

처음에 n개의 수를 입력받고 나면

길이 n짜리 리스트를 만들어 리스트의 각 자리에 그 자리까지의 누적합을 저장한 후에

각 자리의 누적합에서 빼주는 방식으로 구간합을 구하면 된다.

 

이를 파이썬으로 나타낸 코드는 다음과 같다.

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nums = list(map(int, input().split()))
pre = [0]
tmp_sum = []
mysum = 0

for i in range(n):
  mysum += nums[i]
  pre.append(mysum)


for i in range(n-m+1):
  tmp_sum.append(pre[i+m] - pre[i])

print(max(tmp_sum))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !