백준 11659 구간 합 구하기 4 (C#)

문제

N개의 수가 있고, M번의 질의 (i, j)마다 i부터 j까지의 합을 출력하는 문제.
처음엔 매 질의마다 반복문으로 더했다가 “이건 시간초과 각이네…” 싶어서 누적 합으로 정리했다.

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

문제 요약

• 입력:

  	 N(수의 개수), M(질의 수)
  
  	 N개의 수
  
  	 M개의 줄에 i j (1-based)

• 출력: 각 질의마다 i ~ j 구간 합

접근: 누적 합(Prefix Sum)

핵심 아이디어는 간단하다.

prefixSum[0] = 0

prefixSum[i] = prefixSum[i-1] + numbers[i-1] (i는 1부터 시작)

구간 합은 한 방에:

sum(i,j)=prefixSum[j]−prefixSum[i−1]

왜 1-based로 prefixSum을 만들까?
→ i=1일 때도 예외 없이 prefixSum[j] - prefixSum[0]으로 처리하려고.
(배열은 기본값이 0으로 초기화되므로 prefixSum[0]은 따로 안 넣어도 0)

이해하기 (예시)

numbers = [5, 4, 3, 2, 1]

• prefixSum = [0, 5, 9, 12, 14, 15]

  	1번째까지 합: 5
  
  	2번째까지 합: 9
  
  	… 5번째까지 합: 15

질의 (2, 4) → prefixSum[4] - prefixSum[1] = 14 - 5 = 9
실제 합 4 + 3 + 2 = 9

작성 코드

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {

        static void Main()
        {

            
            int[] nm = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int n = nm[0];
            int m = nm[1];

            // 숫자 배열
            int[] numbers = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

            // 누적 합 배열 (1-based, 크기 n+1)
            int[] prefixSum = new int[n + 1];
            for (int i = 1; i <= n; i++)
            {
                prefixSum[i] = prefixSum[i - 1] + numbers[i - 1];
            }

            // 쿼리 처리
            StringBuilder sb = new StringBuilder();
            for (int q = 0; q < m; q++)
            {
                int[] range = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                int start = range[0];
                int end = range[1];

                int ans = prefixSum[end] - prefixSum[start - 1];
                sb.AppendLine(ans.ToString());
            }

            // 한 번에 출력
            Console.Write(sb);
        }        
    }
}

내가 한 실수 & 배운 점

처음엔 질의마다 for로 더해서 O(N×M) → 큰 입력에서 시간초과 위험.

1-based 누적 합을 쓰면 start == 1일 때도 예외 처리 없이 깔끔.