C# 2003 수들의 합2

투포인터 알고리즘

순차적으로 접근해야 할 때 두 개의 점(시작점과 끝점)의 위치를 기록하며 처리하는 알고리즘

1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다

2. 현재 부분 합이 m과 같다면 카운트한다

3. 현재 부분 합이 m보다 작다면 end를 1 증가시킨다

4. 현재 부분합이 m보다 크거나 같다면 start를 1 증가시킨다

5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다

using System;

namespace _2003
{
    class Program
    {
        static void Main(string[] args)
        {
            //수열의 크기 n, 경우의 수를 구할 합 m
            int[] nm = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
            int n = nm[0];
            int m = nm[1];
            int[] A = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

            int count = 0;
            int sum = 0;
            int end = 0;

            for(int i = 0; i < n; i++)
            {
                //현재 합이 m보다 작고 끝점이 n보다 작은 동안 반복
                while (sum < m && end < n)
                {
                    sum += A[end];
                    end++;
                }
                if (sum == m)
                    count++;
                //현재 합이 m보다 클 경우 
                //시작점(i)의 위치를 옮기기 전에 
                //A[i]의 값을 합에서 미리 뺀다
                sum -= A[i];
            }
            Console.WriteLine(count);
        }
    }
}

 

참고

https://youtu.be/ttLRltNDiCo

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

2003번: 수들의 합 2