백준 구간 합 구하기4 파이썬

한문제만 더풀면 백준 골드티어 달성이기에 안쉬고 계속 문제풀이를 달려보도록한다

 

문제를 보자마자 든 생각은 이게 실버..3? 브론즈 문제 수준 아닌가

 

곧바로 구현하고 제출해보았다

import sys
input=sys.stdin.readline
N,M=map(int,input().split()) # N숫자의 길이, M문제의 개수
num=list(map(int,input().split())) # 숫자
for i in range(M):
    a,b=map(int,input().split())
    print(sum(num[a-1:b]))

시간초과가 떳다 

혹시몰라 파이파이3으로도 제출해보았는데 똑같이 시간초과가 났다

 

단계별로 풀어보기에 있는 도움말을 보면

누적합 테크닉을 사용한다고한다

 

저장해놓고 가져다 써서 시간을 아끼는것이 아닐까

그렇다면 어떻게?

현재 문제와 가장 비슷한 과거의 문제를 찾아서 최대한 가져다 쓰는 방식으로?

그러면 가장 비슷한거 찾는게 시간이 더 오래걸릴것같은데..

 

모르겠당ㅋ 답봐야징 어차피 처음 접하는 개념이기도 하고

---

개념이해 

말그대로 누적합이였다 미리 요소 전체를 누적해서 점차 더해나가고 그걸 1차원 배열에 기록해놓는다 

1 2 3 4 5 6 7 8 9 가 숫자로 입력으로 들어왔다고 치자

문제로 3 8이들어오면

일단 8까지의 누적합을 불러온다 36이다

3부터 더했으니까 2까지의 누적합을뺀다 답은 33이다

N번만큼의 더하기만하면 모든문제를 한번의 연산으로 풀수있다 와우!!

 

간단한 방법이지만 내가 생각치도 못했던 방법.. 이것이 누적합인가...

 

제출

# import sys
# input=sys.stdin.readline
N,M=map(int,input().split()) # N숫자의 길이, M문제의 개수
sum_data = [0 for i in range(N+1)]

for num, d in enumerate(list(map(int, input().split()))): 
    sum_data[num+1] = sum_data[num] + d

for i in range(M):
    a,b=map(int,input().split())
    print(sum_data[b]-sum_data[a-1])

정답

 

그리고 백준 골드티어 달성!

앞으로도 많이 배우겠습니다

 

정보) 단계별로풀어보기만 풀었을때 17단계 1번문제까지 풀면 백준 골드가 된다