백준 - 2003번(수들의 합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이 되는 경우의 수를 구하는 프로그램을 작성하시오.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

        int N = Integer.parseInt(tokenizer.nextToken());    // 수의 개수
        int M = Integer.parseInt(tokenizer.nextToken());    // 목표 수

        tokenizer = new StringTokenizer(reader.readLine());
        int[] num = new int[N];
        for (int i = 0; i < N; i++) {
            num[i] = Integer.parseInt(tokenizer.nextToken());
        }

        int left = 0, right = 0;    // left가 증가 -> 수 감소, right가 증가 -> 수 증가
        int sum = num[right];
        int cnt = 0;

        while (true) {
            if (sum < M) {
                ++right;
                if (right >= N) break;
                sum += num[right];
            }
            else if (sum > M) sum -= num[left++];
            else {
                cnt++;
                sum -= num[left++];
            }
        }

        System.out.println(cnt);
    }

}

• 투포인터의 기본 문제같다.
• 비슷한 문제를 책에서 보고 풀어본 적이 있어서 비교적 빨리 풀 수 있었는데, 무작정 과거의 기억을 떠올려 문제를 풀려고 하니 조건을 이상하게 처음에 부여했다. 다시 생각해서 무한루프를 돌리고 right가 인덱스 범위를 넘어가면 종료하도록 하였다.