BOJ 2559 수열 - python

이런 문제..

 

처음의 풀이.

from sys import stdin

def main():
  def input():
    return stdin.readline().rstrip()
    
  N,K = map(int,input().split())

  ls1= list(map(int,input().split()))
  ls2 = []

  sum1 = 0

  for i in range(N-K+1):
    for j in range(K):
      sum1 += ls1[i+j] 

    ls2.append(sum1)
    sum1 = 0

  print(max(ls2))
  


if __name__ == "__main__":
  main()

하지만 시간 복잡도상 N*K 최악의 경우 N ^2 이기 때문에 입력값이 100000인 이상 시간 초과를 피할 수 없다..

 

다음 풀이.

from sys import stdin

def main():
  def input():
    return stdin.readline().rstrip()
    
  N,K = map(int,input().split())

  ls1= list(map(int,input().split()))
  ls2 = []

  sum1 =0

  #중복되는 값을 줄인다. 

  
  for i in range(K):
    sum1 += ls1[i] 

  
  ls2.append(sum1)
  
  for i in range(N-K):
    ls2.append(ls2[i]-ls1[i]+ls1[i+K])

  print(max(ls2))
  


if __name__ == "__main__":
  main()

알고리즘의 기본 아이디어는 중복을 줄여 비효율을 개선한다 이다.

문제를 읽어보면 앞의 결과값을 이용해 연산횟수를 획기적으로 줄여줄 수 있는데, 결국 N과 K가 아무리 바뀌더라도, 먼저의 계산값에서 가장 앞에 위치했던 항의 값을 빼고, 또 그 범위에 새로 들어오는 숫자를 더해주면 된다.

이런식으로 K회 반복될 연산을, 2회로 줄였다.

ls2에 첫번쨰 결과값을 append 시키고, 위의 내용대로 -ls1[i] + ls1[i+k]를 반복 결과값 리스트를 만들고

max로 답을 출력했다.