2075번 문제

문제

풀이

투포인터를 이용하여 쉽게 풀 수 있다.
포인터 s(start), e(end)를 따라가면서 총합이 M이 되는 경우의 수를 카운트 하면 된다.

• int[] arr : 수열
• int cnt : M이 되는 경우의 수
• int tmp : 현재 합

1. 현재 합이 M보다 작다면 e를 증가시키고 현재 합에 더한다.
2. 현재 합이 M과 같다면 cnt를 늘리고, e를 증가시키고 현재 합에 더한다.
3. 현재 합이 M보다 크다면 s를 현재 합에서 빼고, 증가시킨다.
4. 단, e가 배열 끝까지 도달했을 경우 (e를 더 증가시킬 수 없으므로) s만 계속해서 ++; 해주면서 M이 되는 경우가 있다면 카운트 해준다.

최종 제출 코드

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

public class Main {
    public static void main(String[] args) throws Exception{
        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());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int s=0, e=0;
        int cnt = 0;
        int tmp = arr[0];
        while(s < N) {
            if(e < N-1) {
                if(tmp > M) {
                    tmp -= arr[s];
                    s++;
                } else {
                    if(tmp == M) cnt++;
                    e++;
                    tmp += arr[e];
                }
            } else {
                if(tmp == M) {
                    cnt++;
                }
                tmp -= arr[s];
                s++;
            }
        }
        System.out.println(cnt);
    }
}

세상에 이런 문제만 있다면 참 좋겠다