[백준/C++/JS] 2003번 수들의 합2

[백준] 2003번. 수들의 합2

1. 문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

3. 출력

첫째 줄에 경우의 수를 출력한다.

4. 풀이

• 기본적인 투 포인터 문제.
• right 인덱스를 증가시키면서 sum에 해당하는 배열의 값을 추가한다.
• sum의 값이 우리가 찾아야 하는 값보다 커지면 left를 증가시키면서 sum이 m보다 작아질 때까지 left에 해당하는 값을 sum에서 빼준다.
• left까지 모두 조절한 후, 현재 sum 값이 m과 같은지 확인해주고 같다면 answer 값을 1 증가시켜준다.

5. 처음 코드와 달라진 점

• null

6. 코드 - cpp, js

자바스크립트 코드는 백준에서 확인하지 않았습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int arr[10000];

int main()
{
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

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

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

    while (m < sum)
      sum -= arr[lt++];
    answer += sum == m ? 1 : 0;
  }
  cout << answer;
}

function solution(nums, m) {
  let answer = 0;
  let sum = 0;
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    while (m < sum) {
      sum -= nums[left++];
    }
    answer += sum === m ? 1 : 0;
  }

  return answer;
}