[백준] 2003 - 수들의 합 2

1. 문제

2003번: 수들의 합 2

2. 개요

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다.

이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

입력받은 수열의 누적합을 구해 배열로 만들어둔다. (sums)

누적합 배열을 l, r 두 포인터로 탐색하며 sums[r] - sums[l]의 값을 M과 비교해나간다.

M과 같다면 답을 1씩 늘려주고 탐색이 끝나면 답을 출력한다.

3-2. Python

import sys

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

nums = list(map(int, sys.stdin.readline().split()))

sums = []
sums.append(0)

for i in range(N):
    sums.append(sums[-1] + nums[i])

l, r = 0, 1
answer = 0

while l <= r and r < N + 1:
    result = sums[r] - sums[l]

    if result == M:
        answer += 1
        l += 1
        r += 1

    elif result < M:
        r += 1

    else:
        l += 1

print(answer)

3-3. C#

namespace boj_2003
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]), M = int.Parse(input[1]);

            int[] nums = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
            long[] sums = new long[N + 1];

            for (int i = 0; i < N; i++)
                sums[i + 1] = sums[i] + nums[i];

            int l = 0, r = 1, answer = 0;

            while (l <= r && r < N + 1)
            {
                long result = sums[r] - sums[l];

                if (result == M)
                {
                    answer++;
                    l++;
                    r++;
                }

                else if (result < M)
                    r++;

                else
                    l++;
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}