[백준 알고리즘] 11659. 구간 합 구하기 4 _ 파이썬

 

 

 

 

구간 합 구하기 문제입니다

 

구간 합인 경우 누적합을 이용하면 훨씬 빠릅니다!!

 

처음에는 그냥 for문을 돌려 그때그때 마다 sum을 계산하도록 하는 코드를 작성하였습니다.

 

그렇게 하니 채점은 저에게 시간초과를 선물해주더군요ㅠㅠ 

 

 

 

 

 

 

- 👨‍🎓 TIL

 

→ 함수가 1000번 이상 돌면 파이썬 내에서 recursionerror가 생겨 런타임 오류가 나타나므로 1000번이 돌아가지 않도록 코드를 짜거나, sys.setrecursionlimit()를 사용해 최대 재귀 깊이를 바꿔준다.(스터디장님께서는 꼼수라며..ㅎㅎ 더 나은 알고리즘을 고안해내기를 추천하셨다!)

 

→ 여러번 합을 계산하도록 하는 게 아니라, 한번 누적합을 계산해놓고 필요한 수를 추출하여 빼주는 것이 더 빠르다.

 

→ arr = [0] + list(map(int, input().split())) : 입력받을 때 리스트의 첫번째 값을 0으로 만들어주고 싶다면 리스트 concatenate를 활용하면 좋다!!

(이건 종종 유용하게 쓰일 것 같다!!)

 

 

 

import sys
sys.setrecursionlimit(100000)

# 구간합
def prefix_sum(data):
    s1 = 0
    result = [0]
    for i in data:
        s1 += i
        result.append(s1)
    return result


N, M = map(int, sys.stdin.readline().split())
nums = list(map(int, sys.stdin.readline().split()))
sums = prefix_sum(nums)

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    print(sums[B] - sums[A - 1])

 

누적합으로 바꾼 코드입니다.

 

하지만 런타임 에러가 다시 떴어요ㅠㅠ

 

구글링 끝에 알아낸 방법은 아래의 2줄을 추가해주는 것이었습니다.

import sys
sys.setrecursionlimit(100000)

 

 

최대 깊이 문제가 없도록 다른 분들의 코드를 참고하여 다시 한번 짜보았는데요.

 

 

 

 

import sys

N, M = map(int, sys.stdin.readline().split())
nums = [0] + list(map(int, sys.stdin.readline().split()))

for i in range(1, len(nums)):
    nums[i] += nums[i-1]

for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    print(nums[B] - nums[A - 1])

 

따로 함수를 불러내지 않고 for문으로 돌려 초기 nums를 누적합 nums로 바꿔주니

 

런타임에러가 발생하지 않고, 오히려 이전보다 더 빨라진 코드가 되었습니다!!

 

 

 

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4