[알고리즘 문제 풀기] 합 구하기(11441)

1. 문제 풀이 아이디어

• 누적 합 배열을 사용하여 구간 합을 계산하여 문제를 해결할 수 있다.

2. 나의 정답 코드

using System.Text;
StringBuilder sb = new StringBuilder();

using (StreamReader sr = new(Console.OpenStandardInput()))
using (StreamWriter sw = new(Console.OpenStandardOutput()))
{
    int n = int.Parse(sr.ReadLine());
    int[] a = new int[n + 1];
    string[] split = sr.ReadLine().Split();
    for (int i = 0; i < n; i++)
    {
        a[i + 1] = int.Parse(split[i]) + a[i];
    }
    int m = int.Parse(sr.ReadLine());

    while (m > 0)
    {
        split = sr.ReadLine().Split();
        int i = int.Parse(split[0]) - 1;
        int j = int.Parse(split[1]);
        sb.AppendLine((a[j] - a[i]).ToString());
        m--;
    }
    sw.Write(sb);
}

3. 정리

• int[] a = new int[n + 1]에서 누적 합 배열을 선언한다.

• for 문을 사용하여 a[i + 1] = int.Parse(split[i]) + a[i]로 누적 합을 계산한다.

• while (m > 0)에서 m개의 쿼리를 처리하며, a[j] - a[i]를 이용해 구간 합을 출력한다.