BAEKJOON_2559 "수열" PYTHON

[백준] 2559번 Python 파이썬

 

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

2559번: 수열

< 시간 초과 코드 >

 

아래의 코드는 O(nk)의 시간 복잡도를 갖기 때문에 n과 k의 크기가 클 경우 오랜 시간이 걸린다. 

import sys

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

lt = [[0] for i in range(n - k + 1)]

for i in range(n - k + 1):
    lt[i] = sum(tp[i:i+k])

print(max(lt))

< 성공한 코드 >

 

아래의 코드는 누적합(Prefix Sum)을 이용하여 입력된 리스트 tp를 한 번만 반복하고,

각 요소마다 상수 시간 연산을 수행하기 때문에시간복잡도 O(n)을 갖는다. 

import sys

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

lt = [0]*(n - k + 1)
lt[0] = sum(tp[:k])

for i in range(1, n - k + 1):
    lt[i] = lt[i-1] - tp[i-1] + tp[i+k-1]

print(max(lt))

혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.