[백준 2003] 수들의 합 2 (C#, C++) - soo:bak

문제 링크

2003번 - 수들의 합 2

설명

자연수로 이루어진 수열에서 연속한 부분 수열의 합이 정확히 M이 되는 경우의 수를 구하는 문제입니다.

접근법

수열의 모든 원소가 자연수이므로, 구간 합은 오른쪽 포인터를 늘리면 커지고 왼쪽 포인터를 줄이면 작아집니다. 이 성질을 이용해 투 포인터(슬라이딩 윈도우) 로 연속 구간을 관리할 수 있습니다.

오른쪽 포인터를 한 칸씩 늘리며 현재 구간 합에 값을 더합니다. 합이 M보다 커지면, 다시 M 이하가 될 때까지 왼쪽 포인터를 움직이며 값을 뺍니다.

이 과정을 반복하면서 합이 정확히 M이 되는 순간마다 경우의 수를 하나씩 증가시키면 됩니다.

---

Code

C#

using System;
using System.Linq;

class Program {
  static void Main() {
    int[] nm = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
    int n = nm[0];
    int m = nm[1];
    int[] arr = Console.ReadLine()!.Split().Select(int.Parse).ToArray();

    int left = 0;
    long sum = 0;
    int count = 0;

    for (int right = 0; right < n; right++) {
      sum += arr[right];

      while (sum > m && left <= right) {
        sum -= arr[left];
        left++;
      }

      if (sum == m)
        count++;
    }

    Console.WriteLine(count);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<int> arr(n);
  for (int i = 0; i < n; i++)
    cin >> arr[i];

  int left = 0;
  long long sum = 0;
  int count = 0;

  for (int right = 0; right < n; right++) {
    sum += arr[right];

    while (sum > m && left <= right) {
      sum -= arr[left];
      left++;
    }

    if (sum == m)
      count++;
  }

  cout << count << "\n";

  return 0;
}