[백준] 11659번 : 구간 합 구하기 4 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11659번: 구간 합 구하기 4

 

1. 문제 설명

2. 풀이과정

문제에서 수의 개수와 합을 구해야 하는 횟수는 최대 100,000이다.

게다가 구간마다 합을 매번 계산하면 0.5초 안에 모든 구간 합 계산을 끝낼 수 없다.

하여 구간 합을 이용해 문제를 해결한다.

 

1. N개의 수를 입력받음과 동시에 합 배열을 생성한다. S[i] = S[i - 1] + A[i]
2. 구간 i ~ j가 주어지면 구간 합을 구하는 공식으로 정답을 출력한다. S[j] - S[i - 1]

슈도코드

1. N(숫자 개수), M(질의 개수)
2. numbers 변수에 숫자 데이터 저장
3. perfix_sum 합 배열 변수 선언
4. for 저장한 숫자 데이터 차례대로 탐색 : 합 배열에서 이전 값에 현재 숫자 데이터 더해 값 저장
5. for 질의 개수만큼 반복
6. 질의 범위 받기 (start ~ end)
7. 구간 합 출력하기 (perfix_sum[end] - perfix_sum[start - 1])

반응형

3. 소스코드

import sys

N, M = map(int, sys.stdin.readline().split())
numbers = list(map(int, sys.stdin.readline().split()))

perfix_sum = [0] * (N + 1)
for i in range(1, N + 1):
    perfix_sum[i] = perfix_sum[i - 1] + numbers[i - 1]
    
for i in range(M):
    start, end = map(int, sys.stdin.readline().split())
    print(perfix_sum[end] - perfix_sum[start - 1])