[BOJ 2003] 수들의 합 2

문제

수들의 합 2

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

 

 

풀이

설명

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있을 때, 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 문제입니다.

 

투 포인터 알고리즘을 이용해 풀 수 있습니다.

 

start와 end의 인덱스를 0으로 초기화하고, start부터 end까지의 원소 합과 M을 비교합니다.

합이 M보다 크면 start를 증가시키고, M보다 작으면 end를 증가시킵니다.

 

예시 코드

function solution() {
  const [N, M] = input().split(" ").map(Number);
  const A = input().split(" ").map(Number);
  let cnt = 0;
  let start = 0;
  let end = 0;
  let sum = 0;

  while (end <= N) {
    if (sum === M) {
      cnt++;
      sum -= A[start];
      start++;
    } else if (sum < M) {
      sum += A[end];
      end++;
    } else {
      sum -= A[start];
      start++;
    }
  }

  return cnt;
}