백준 11659 -구간 합

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

11659번: 구간 합 구하기 4

 

 

 

 

 

 

시간 초과난 나의 코드 1

n,m=map(int,input().split())
arr=list(map(int,input().split()))

for _ in range(m):
    a,b=map(int,input().split())
    print(sum(arr[a-1:b]))

시간복잡도 O(n*M)으로 초과 (sum함수로 슬라이싱 연산시 O(N)의 시간 복잡도를 가진다.

 

 

시간 초과난 나의 코드 2

import sys

n,m=map(int,input().split())
arr=list(map(int,sys.stdin.readline().split()))

summ=0
prefix_sum=[0]
for x in arr:
    summ+=x
    prefix_sum.append(summ)



for _ in range(m):
    a,b=map(int,input().split())
    print(prefix_sum[b]-prefix_sum[a-1])

슬라이싱 연산 대신 구간합을 리스트를 사용하였으나 마지막 for문에서 readlined을 사용하지 않고 처음 엉뚱한곳에서 사용해서 초과 

 

 

 

 

정답코드

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
arr=list(map(int,input().split()))

summ=0
prefix_sum=[0]
for x in arr:
    summ+=x
    prefix_sum.append(summ)



for _ in range(m):
    a,b=map(int,input().split())
    print(prefix_sum[b]-prefix_sum[a-1])