[BOJ] 2015 수들의 합 4 - JAVA

1. 문제

2015번: 수들의 합 4

A[1], A[2], ..., A[N]의 N개의 정수가 저장되어 있는 배열이 있다. 이 배열 A의 부분합이란 1 ≤ i ≤ j ≤ N인 정수 i와 j에 대해 A[i]부터 A[j]까지의 합을 말한다.

N과 A[1], A[2], ..., A[N]이 주어졌을 때, 이러한 N×(N+1)/2개의 부분합 중 합이 K인 것이 몇 개나 있는지를 구하는 프로그램을 작성하시오.

---

2. 풀이

1.  sum을 누적합 배열이라고 쳤을 때, i부터 j까지의 합은 sum[j]-sum[i-1]이다. 이 값이 K가 되어야 한다.

sum[j]-sum[i-1] = K (N>=j>=i>=1)

sum[j] - K = sum[i-1]

2.  누적합 배열을 차례대로 탐색하면서, sum[j]-K값이 이전 누적합 중에 존재한다면 그 개수만큼 answer에 더한다.

3.  이전 누적합과 그 개수는 HashMap을 이용해서 저장한다. 먼저 sum[j]-K를 탐색하고, 그 뒤에 sum[j]를 map에 더하는 방식이다.

4.  이때, i>=1이기 때문에 sum[i-1] = sum[1-1] =  sum[0]을 탐색하기 전에 미리 map에 더해야 한다.

import java.io.*;
import java.util.*;

public class BOJ_2015_수들의합4 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());

      Map<Integer, Integer> map = new HashMap<>();
      int[] sum = new int[N + 1];
      st = new StringTokenizer(in.readLine());
      for (int i = 1; i <= N; i++) {
         sum[i] = sum[i - 1] + Integer.parseInt(st.nextToken());
      }

      map.put(0,1);

      long answer = 0;
      for (int j = 1; j <= N; j++) {
         answer += map.getOrDefault(sum[j] - K, 0);
         map.put(sum[j], map.getOrDefault(sum[j], 0) + 1);
      }

      System.out.println(answer);
   }
}

---

3. 결과

sum[j] = sum[i] + K(j>=i)를 활용했다가 틀렸다. (answer 타입 문제도 한 번 있었다)

이때는 i를 기준점으로 잡았기 때문에 i 이후의 누적합과만 비교해야하는데, 미리 sum요소를 map에다 넣으면 이전의 누적합과 개수를 구분할 수 없어서 이 방식보다는 j를 활용한 방식을 선택해야 한다.