[백준/Python] 11659번: 구간 합 구하기 4

1. 문제 분석

• 핵심: N개의 수가 주어졌을 때, i번째 수부터 j번째 수까지의 합을 구하는 질문(M)을 해결하기.
• 입력: N (데이터 개수), M (질문 개수), 그리고 N개의 숫자들.
• 조건: N, M <= 100,000.

---

2. 접근 방식

1. for문을 돌려 합을 구하는 방식
2. 시간 초과 문제
3. 합 배열로 구하기

---

3. 내 풀이 (Code)

N=int(input())
M=int(input())

number=list(map(int,input().split()))
for _ in range(M):
    sum=0
    i=int(input())
    j=int(input())
    
    for k in range(i-1,j):
        sum=sum+number[k]

---

4. 코드 리뷰 및 학습 포인트

✅ 정답 풀이 - 합 배열 (Prefix Sum)

매번 더하는 대신, "미리 다 더해두면 어떨까?"라는 생각에서 출발하는 기법입니다.

① 합 배열(S) 만들기

인덱스에 "0번부터 해당 위치까지의 누적 합"이라는 의미를 부여합니다.

• S[i] = S[i-1] + A[i-1] (직전까지의 누적 합 + 현재 값)

② 구간 합 공식

합 배열을 만들어 두면 어떤 구간의 합이든 단 한 번의 뺄셈으로 구할 수 있습니다.

• i부터 j까지의 합 = S[j] - S[i-1]

import sys

# 1. 빠른 입력 설정
input = sys.stdin.readline

# 2. N(데이터 개수)과 M(질문 개수) 입력
N, M = map(int, input().split())

# 3. 원본 숫자 리스트 입력
numbers = list(map(int, input().split()))

# 4. 합 배열(Prefix Sum) 생성
# 계산의 편의를 위해 맨 앞에 0을 추가 (인덱스 맞추기용)
prefix_sum = [0]
temp = 0
for n in numbers:
    temp += n
    prefix_sum.append(temp)

# 5. M번의 구간 합 질문 처리
for _ in range(M):
    i, j = map(int, input().split())
    # 공식 적용: S[j] - S[i-1]
    # 질문이 아무리 많아도 뺄셈 한 번(O(1))에 끝!
    print(prefix_sum[j] - prefix_sum[i-1])

✅ 시간 복잡도

• O(N * M)의 100억 번 연산을 O(N + M)의 20만 번 연산으로 줄였습니다.