11659: 구간 합 구하기 4

문제

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

풀이 1 (오답: 시간 초과)

N, M = map(int, input().split())
arr = [0] + list(map(int, input().split()))

for _ in range(M):
    i, j = map(int, input().split())
    print(sum(arr[i:j+1]))

이렇게 쉽게 풀릴 리가 없지

풀이 2

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [0] + list(map(int, input().split()))
sum_list = [0] * (N+1)

for i in range(1, N+1):
    sum_list[i] = sum_list[i-1] + arr[i]

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

• input = sys.stdin.readline 없이 제출했을 때 시간 초과 나서 알고리즘 문제인 줄 알았는데, 그게 아니었다.

풀이 3

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))
total = [0]

tmp = 0
for i in arr:
    tmp += i
    total.append(tmp)

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

• Go동수님 풀이를 참고하였다.
• 역시 sys.stdin.readline을 사용해야만 시간 초과가 발생하지 않는다.

---

오늘의 교훈

• 여러 줄 입력 받을 때는 무조건 sys.stdin.readline을 쓰자.

참고 자료

• https://116116.tistory.com/entry/백준-11659번-구간-합-구하기-4-python