[BaekJoon] 백준 11659번 구간 합 구하기 4

[BaekJoon] 백준 11659번 구간 합 구하기 4

 

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

 

내코드

 

우선 문제를 처음 봤을 때 주어진 숫자를 가지고 정직하게 풀었을 때 시간이 부족할 것이라는 생각이 들었다. N개의 숫자들 중에서 특정 구간을 M번 더해야 하는 경우를 생각해보면, 최악의 경우 100,000(처음부터 끝까지 모든 수(N의 최대값)를 더했을 때 덧셈의 횟수) X 100,000(합을 구해야 하는 횟수 M의 최대값)은 1억을 넘어가고 1억을 약 1초라고 했을 때 한참 넘어가기 때문이다.

 

그래서 생각한 방식이 첫번째 수부터 n번째 수까지 더한게 f(n)이라고 하면 i번째~j번째 구간의 합은 f(j) - f(i - 1)로 계산하자는 것이다. 이 방식으로 하면 위에서 언급한 최악의 경우도 100,000(1~1, 1~2, 1~3...구간 합 구해놓는 횟수) + 100,000(합을 구해야 하는 횟수 M의 최대값) 밖에 들지 않는다.

 

+ 계속 시간 초과가 나서 검색을 해봤는데, 파이썬의 경우 input()이 아닌 sys.stdin.readline()을 써야 시간초과가 나지 않는다고 한다.

 

+ 궁금해서 찾아봤는데 파이썬으로 알고리즘 문제를 풀때 조금이나마 시간을 줄일 수 있는 방법 3가지를 알게 되었다.

1. input()보다는 sys.readline()을 쓰자.

2. 빈 리스트에 append()로 추가하는 것보단 입력 받을 개수 만큼 초기화된 리스트에 인덱스를 이용해서 접근해서 그 위치에 직접 입력받자.

3. 줄바꿈 할때엔 print()가 아니라 '\n', for문 마다 출력하지 말고 문자열 변수에 저장해놓고 한 번에 출력하자.

 

 

코드블럭

import sys
input = sys.stdin.readline

N, M = map(int, input().split(" "))
arr = list(map(int, input().split(" ")))
result = [0 for _ in range(N)]

for i in range(N):
    if i == 0:
        result[i] = arr[i]
    else:
        result[i] = result[i - 1] + arr[i]

for _ in range(M):
    i, j = map(int, input().split(" "))
    if i == 1:
        print(result[j - 1])
    else:
        print(result[j - 1] - result[i - 2])

 

참고

https://breakcoding.tistory.com/109