[algorithm] 백준 11659 - 구간 합 구하기 4

[algorithm] 백준 11659 - 구간 합 구하기 4

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 11659번 문제 - 구간 합 구하기 4 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 11659

 

백준 11659번 구간 합 구하기 4 문제 보러가기

 

반응형

 

문제 해석

 

문제에서 주어지는 수열과 구간을 해당하는 구간의 합을 구하는 문제입니다.

단, 1초안에 문제를 모두 수행해야하므로 시간복잡도를 신경써야합니다.

힌트 : 구간의 합을 계속해서 계산하는것 보다 미리 계산해두고 사용하는건 어떨까요?

 

풀이

 

# 11659 구간 합 구하기 4
import sys

cnt, N = map(int, sys.stdin.readline().split())
number = list(map(int, sys.stdin.readline().split()))
sum_list = [0]
tmp = 0

for i in number:
    tmp += i
    sum_list.append(tmp)

for _ in range(N):
    a, b = map(int, sys.stdin.readline().split())
    print(sum_list[b] - sum_list[a-1])

 

풀이 해석 및 팁

 

시간초과를 피하기위해서 수열의 인덱스를 하나씩 늘려가면서 반복문으로 구간 구간의 합을 미리

구해놓는 방법을 사용했습니다.

sum_list 라는 리스트에 구간 별 합을 요소로 추가시켜주었고

이를 활용해서 문제에서 원하는 구간의 합을 구해 출력하면서 문제를 해결했습니다.

---

여기까지 백준 11659번 구간 합 구하기 4 문제 풀이였습니다.

이번 문제의 정답률은 39% 정도입니다.

 

궁금하신 점은 댓글로 남겨주시기 바랍니다.

 

감사합니다.