[BOJ] 2015. 수들의 합4

[작성일]

• 2022-03-09

[분류]

• 누적합
• map
  
  
  

[문제링크]

• https://www.acmicpc.net/problem/2015
  
  
  

[요구사항]

• 부분합이 K인 경우가 총 몇 개인지 구하라.
  
  
  

[풀이]

누적 합을 구한 후에, hashmap을 이용해서 K와 동일한 부분 합의 개수를 구한다.

우선, 누적합 중에서 K와 동일한 갯수를 정답에 더해준다.
이제, 다시 반복문을 돈다. 반복문을 돌면서 hashmap에 누적합을 key로 하고, 갯수를 value로 하는 데이터를 추가해준다.
데이터를 추가하기 전에, 검사를 해서 정답에 또 추가해주는 과정이 핵심이다.
현재 i번째까지 누적합을 A, A-K를 B라고 하자.
map에 B가 있는 경우 그 경우만큼 정답 개수에 추가해준다.

왜?
B의 개수가 의미하는 것은 지금 i번째까지 모두 더한 누적합 전까지 B가 되는 경우의 수이다.
즉, 그 경우가 만들어지는 경우는 i번째 누적합을 구한 지금 시점보다는 무조건 앞에 일어났다는 의미이다. 현재 A이고 A - B는 곧 K가 될 수 있기 때문에 현재까지 B가 된 경우의 수를 모두 정답에 더하는 것은 논리적으로 맞다.

이렇게 답을 구하면 정답이 도출된다.

[코드]

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

class Main {
    static int N;
    static int K;
    static int[] sum;
    static Map<Integer, Long> map = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long answer = 0;

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        sum = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());

            // 1. 누적합 중에서 K되면 answer에 더해준다.
            if (sum[i] == K) answer++;
        }

        for (int i = 1; i <= N; i++) {
            // 3. 누적된 값이 A이고 A-K가 B라고 하자.
            //    B에 해당하는 경우가 있는 경우(즉, map에 value가 있는 경우)만큼 곧, K가 될 수 있음을 의미한다.
            //    왜냐하면, 지금 i까지 더한 누적합에서 B가 되는 index가 j라고 하면 sum[i] - sum[j] = K가 되기 때문이다.
            //    즉, 갯수를 구하려면 map의 value만큼이다.
            if(map.containsKey(sum[i] - K)) {
                answer += map.get(sum[i] - K);
            }

            // 2. 누적합을 map에 추가해준다.
            if (map.containsKey(sum[i])) {
                map.put(sum[i], map.get(sum[i]) + 1);
            } else {
                map.put(sum[i], 1L);
            }
        }

        System.out.println(answer);
    }
}