[Java] [백준 2003][투 포인터] 수들의합 2

문제

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

입력

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

 

 

---

 

🌈 풀이 후기

• 전형적인 투 포인터 문제입니다. 투 포인터 개념을 익히기에 좋은 문제인것 같습니다.

  https://www.youtube.com/watch?v=rI8NRQsAS_s&ab_channel=동빈나

  제가 좋아하는 동빈나에서 자세히 알려주고 있습니다 ㅎㅎ 심심하면 봐보세요!

• 비슷하게 잘 나오는 문제로 누적합 문제가 있는데 백준 11659 입니다. 한번 풀어보세요!

👩‍🏫 문제 풀이

알고리즘 - 투 포인터

 

1. start와 end를 초기에 0을 잡는다.
2. start와 end 사이의 값이 M보다 작다면 end를 1 증가시킨다. (end는 배열의 끝까지 검사한다.)
3. 만약 start와 end의 합이 M보다 크거나 같다면 M과 같은지 검사한다. 3-1. 같다면 경우의 수를 1 증가시킨다.
4. start와 end의 합에서 start값을 빼준다. 그리고 start를 1 증가시켜준다.

package com.Boj.seoul8.week4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 투 포인터 O(N) 
// 연속된 수열의 합.
public class BOJ_S3_2003_수들의합2 {
	static int N, M;
	static int[] A;
	static int cnt = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		A = new int[N];
		st = new StringTokenizer(br.readLine(), " ");

		for (int i = 0; i < N; i++)
			A[i] = Integer.parseInt(st.nextToken());

		twoPointer();
		System.out.println(cnt);
	}

	private static void twoPointer() {
		int sum = 0;
		int end = 0;
		for (int start = 0; start < N; start++) {
			while (sum < M && end < N)
				sum += A[end++];

			if (sum == M)
				cnt++;

			sum -= A[start];
		}

	}

}