BOJ 11659 - 구간 합 구하기 4

 

백준에서 처음 풀어보는 문제..

일단 ide가 없어 굉장히 러프하고, 발상보다 시간복잡도, 알고리즘을 고려해야하는 문제이다.

 

언뜻 보면 굉장히 간단한 문제처럼 보인다. 하지만 제한사항에 n,m이 100,000 과 100,000 최악의 경우 시간복잡도가 오버될 수 있음을 볼 수 있다.

 

 

누적합을 배우기전 나의 답.

 

N, M = input().split()
ls1 = list(map(int,input().split()))
ls2 = []
sum1 = 0



for k in range(int(M)):
  i,j = input().split()
  sum1 = sum(ls1[int(i)-1:int(j)])
  ls2.append(sum1)

for i in ls2:
  print(i)

일단 백준이 처음이라 그런지 input에 대해 시간복잡도를 줄이는 법을 모르고 .. 

input을 받을떄 map을 활용해 int로 만드는 것도 미숙하다.

그리고 결정적으로 시간초과가 됐다.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
ls1 = list(map(int,input().split()))



for i in range(N-1):
    ls1[i+1] += ls1[i]
    
ls1 = [0] + ls1

for k in range(M):
    i,j = map(int,input().split())
    print(ls1[j]-ls1[i-1])

위의 오류를 수정한 결과.

 

[5,4,3,2,1]에서 합의 식을 만들때는 앞에 [0]을 붙여줬는데,

 

제한 조건을 보면 i,j의 범위가 서로 같을 수도 있음을 알 수 있다.

즉 1,1과 같은 범위를 합해 출력할때는 어떻게 될지 생각해보자.