[백준 / 실버4] 2003 수들의 합 2 (Java)

문제 보기

사용한 것

• 배열의 i 번째 인덱스 ~ j 번째 인덱스 까지의 합을 효율적으로 구하기 위한 누적합
• O(N)으로 배열의 가능한 구간을 탐색하기 위한 투포인터

풀이 방법

• 입력 값으로 누적합을 sum에 저장한다.
• 투포인터와 sum을 사용하여
  • 현재 구간의 합이 m과 같으면 answer 증가, r 증가
  • 현재 구간의 합이 m보다 크면 l 증가
  • 현재 구간의 합이 m보다 작거나 l과 r이 같으면 r 증가

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] sum = new int[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(st.nextToken());
            sum[i] = sum[i - 1] + num;
        }

        // 투포인터
        int answer = 0;
        int l = 0;
        int r = 1;
        while (l < r && r <= n) {
            int diff = sum[r] - sum[l];
            if (diff == m) {
                answer++;
            }
            if (diff > m) {
                l++;
            }
            if (diff <= m || l == r) {
                r++;
            }
        }

        System.out.println(answer);
    }
}