[자바] 백준 2003번: 수들의 합2

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

2003번: 수들의 합 2

 

설 연휴

쉴땐 쉬더라도 쉬운거 한문제정도는 풀어놓고싶었는데

 

아..생각보다 잘 안풀렸다.

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

public class P2003 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());

		int[] arr = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());

		}

		int i = 0, j = 0, count = 0, sum = 0;
		while (i < n) {
			if (sum > m || j == n) {

				sum -= arr[i];
				i++;

			} else if (sum <= m) {

				sum += arr[j];
				j++;
			}

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

		}

		System.out.println(count);

	}

}

투 포인터 문제다.

 

부분수열의 앞부분을 i, 맨 뒷부분을 j라고 하고

부분수열을 구해나간다.

 

sum이m보다 작다면 j를 증가시켜 수열을 늘리고

sum이 m보다 크다면 i를 증가시켜 수열을 줄일 수 있다.

 

sum이 m과 같을 때마다 count를 증가시키고,

마지막에 count를 출력하면 된다.