python 11659 구간 합 구하기 4

📌 문제 정보

• 문제 번호: 11659
• 문제: https://www.acmicpc.net/problem/11659
• 난이도: 실버 3

---

🧩 문제 요약

정수 N개로 이루어진 수열이 주어졌을 때,
i번째 수부터 j번째 수까지의 합을 구하는 프로그램 작성하는 문제.

질문은 M번 주어지며, 각 질문마다 구간의 합을 빠르게 출력해야 함.

---

🧪 예제 입력 / 출력

입력:

5 3 5 4 3 2 1 1 3 2 4 5 5

 

출력:

12 9 1

 

 

설명:

• 1~3번째 수: 5+4+3 = 12
• 2~4번째 수: 4+3+2 = 9
• 5번째 수: 1

---

💡 접근 방식

• 단순히 매번 i부터 j까지 합을 구하면 시간 초과 발생 (최악의 경우 M×N)
• 누적합(Prefix Sum)을 사용하면 빠르게 계산 가능
• 미리 누적합 배열을 만들어두고, 각 쿼리에 대해 **상수 시간 O(1)**에 결과 출력 가능

---

⚙️ 알고리즘 설명

누적합(Prefix Sum) 개념 활용:

• sums[i] = 첫 번째 수부터 i번째 수까지의 합
• i~j 구간의 합 = sums[j] - sums[i-1]
• 0번째 원소는 0으로 초기화해서 인덱스 계산 편하게 처리

이 방법을 쓰면 M개의 쿼리에 대해 각각 O(1) 시간에 답할 수 있음

---

🧑‍💻 코드 구현 (Python)

import sys
input = sys.stdin.readline

# N: 숫자 개수, M: 합을 구해야 하는 횟수
N, M = map(int, input().split())

# 수열 입력
nums = list(map(int, input().split()))

# 누적합 배열 초기화 (0번째는 0으로 두기)
sums = [0]
for i in nums:
    sums.append(sums[-1] + i)

# 각 구간 합 쿼리에 대해 출력
for _ in range(M):
    i, j = map(int, input().split())
    print(sums[j] - sums[i-1])

---

🔁 다른 풀이 / 코드 개선 방향

• itertools.accumulate 활용 가능 (라이브러리 이용 시 좀 더 간결하게 가능)
• 입력이 많은 경우 sys.stdin.readline()은 필수 (입력 속도 중요)
• 구간 합 쿼리가 많을수록 누적합 방식의 효율성 극대화됨

---

⏱️ 시간복잡도 분석

• 누적합 배열 생성: O(N)
• M개의 쿼리 처리: O(M)
• 총 시간복잡도: O(N + M)
• 공간복잡도: O(N) (누적합 배열 크기)

---

📝 결론 및 팁

• 누적합은 구간 합 문제에서 매우 강력한 도구임
• sums[i] = sums[i-1] + nums[i] 형태 잘 기억할 것
• 입력이 많으면 input() 대신 sys.stdin.readline() 사용 권장

유사 문제 추천:

• 백준 10986번: 나머지 합
• 백준 11660번: 구간 합 구하기 5 (2차원 누적합)