📙[Algo] 24.01.27 ~ 24.01.29 알고리즘

알고리즘 문제) BOJ 3673. 나눌 수 있는 부분 수열

3673번: 나눌 수 있는 부분 수열

문제 요약

• 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수 구하기

시간 제한

• 1초

입력

• 테스트 케이스 c (1≤c≤200)
• d(1≤d≤100만) n(1≤n≤5만)
• 수열 원소(1≤원소≤10억)

출력

• d로 나누어 떨어지는 것의 개수

접근법

1. 완전 탐색으로 접근하기
   • 시작 포인트 지정 for문 * 끝 포인트 지정 for문 * 해당 구간까지 더하는 for문쿼리수 ⇒ 5만5만5만200
   ⇒ 2중 for문부터 시간초과가 뜸!!
2. 최적화 하기
   연속합문제처럼 뭔가 더 최적화가 필요하다.
   d로 나누어 떨어지려면 일단 합계가 d의 배수여야 한다.
   2 1 2 1 1 2 1 2 (d=4)
   

   2	1	2	1	2	3	2	1	2
   2
   2	3
   2	3	1
   2	3	1	2
   2	3	1	2	0
   2	3	1	2	0	3
   2	3	1	2	0	3	1
   2	3	1	2	0	3	1	2
   2	3	1	2	0	3	1	2	0

   누적합의 나머지를 기록
   ⇒ d로 나누어 떨어지는 경우 위에서 같은 수끼리 뺄 수 있는 경우의 수를 구한다(nC2).
   0은 0의 개수만큼 더한 거까지 추가!
   ⇒ 위 예시의 경우 총 8가지 = 3 + 1 + 1 + 1 + 2

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int c = Integer.parseInt(br.readLine());

        StringTokenizer st;
        int d, n;
        long cnt;
        long[] arr, remain;
        while (c-- > 0) {
            st = new StringTokenizer(br.readLine());
            d = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());

            arr = new long[n + 1];
            remain = new long[d + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                arr[i] = (arr[i-1] + Integer.parseInt(st.nextToken())) % d;
                remain[(int)arr[i]]++;
            }

            cnt = 0;
            for (int i = 0; i < d ; i++) {
                if(remain[i] >= 2) cnt += (remain[i] * (remain[i] - 1)) / 2;
                if(i == 0) cnt += remain[0];
            }

            sb.append(cnt+"\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2143. 두 배열의 합

2143번: 두 배열의 합

문제 요약

• 각 원소가 정수인 두 배열 A, B가 주어졌을 때
• A의 부 배열 합 + B의 부 배열의 합이 T가 되는 모든 부 배열 쌍의 개수 구하기

시간 제한

• 2초

입력

• T
  • -10억 ~ 10억
• n
  • 1~1,000
• A배열 원소
• m
  • 1~1,000
• B배열 원소
• 각각의 원소는 절대값이 100만 이하의 정수

출력

• 가능한 경우의 수 출력, 없다면 0

접근법

1. 완전 탐색으로 접근하기
   각각 누적합 배열을 구하고, 각각 부배열들의 모든 경우를 구한다.
   그리고 2중 for문을 사용해서 각각 원소들의 합이 T가 되는 경우의수를 더한다.
   ⇒ 최악의 경우 500500*500500 으로 시간초과
2. 최적화 하기
   투포인터를 추가로 적용한다.
   부배열의 후보들을 오름차순 정렬하고,
   A의 부배열의 맨 앞 index에 start point
   B의 부배열의 맨 뒤 index에 end point를 배치한다음
   둘의 합이 T보다 작을 경우 startpoint++, T보다 클 경우 endpoint—를 하며 진행!

코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        int n = Integer.parseInt(br.readLine());
        long[] accA = new long[n + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            accA[i] = accA[i - 1] + Integer.parseInt(st.nextToken());
        }


        int m = Integer.parseInt(br.readLine());
        long[] accB = new long[m + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            accB[i] = accB[i - 1] + Integer.parseInt(st.nextToken());
        }

        ArrayList<Long> subA = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                subA.add(accA[j] - accA[i - 1]);
            }
        }

        ArrayList<Long> subB = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            for (int j = i; j <= m; j++) {
                subB.add(accB[j] - accB[i - 1]);
            }
        }

        Collections.sort(subA);
        Collections.sort(subB);

        int s = 0, e = subB.size() - 1;
        long cnt = 0, sCnt, eCnt;
        while (s < subA.size() && 0 <= e) {
            if (subA.get(s) + subB.get(e) < T) {
                s++;
            } else if (subA.get(s) + subB.get(e) > T) {
                e--;
            } else {
                sCnt = 1;
                while (s + 1 < subA.size() && subA.get(s + 1) + subB.get(e) == T) {
                    sCnt++;
                    s++;
                }
                s++;

                eCnt = 1;
                while (0 < e && subA.get(s - 1) + subB.get(e - 1) == T) {
                    eCnt++;
                    e--;
                }
                e--;

                cnt += sCnt * eCnt;
            }
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2304. 창고 다각형

2304번: 창고 다각형

문제 요약

• N개의 막대 기둥이 일렬로 세워져 있음(폭은 1m)
• 지붕은 수평, 수직으로 구성
  • 지붕의 수평, 수직은 모두 기둥의 윗면, 옆면과 닿을 것
  • 지붕의 가장자리는 땅에 닿을 것
  • 빗물이 고이지 않도록 오목한 부분 없을 것!
• 지붕으로 둘러쌓인 창고 다각형의 넓이 구하기

시간 제한

• 2초

입력

• 기둥 개수 N (1 ≤ N ≤ 1,000)
• N개의 줄에 각 기둥의 위치 정수 L과 높이 정수 H가 주어짐
  • 1≤ L, H ≤ 1,000

출력

• 창고 다각형의 면적은?

접근법

1. 완전 탐색으로 접근했을 때는 가장 높은 기둥을 기준으로 좌측 우측 구역으로 나누고 좌측 기준 왼쪽→오른쪽으로 이동하면서 가장 높은 기둥을 기준으로 넓이를 더해주고, 우측 기준 오른쪽→왼쪽 이동하면서 가장 높은 기둥을 기준으로 넓이를 더해줬다. 그다음 가운데 가장 높은 기둥 높이만큼 최종적으로 더해줘서 답을 구했었음.
2. 이거 역시 최대값이 기준이 되었으므로 내 왼쪽 기준 가장 높은 기둥 높이, 내 오른쪽 기준 가장 높은 기둥 높이들을 미리 기록해두고 사용하면 좋을 듯. ⇒ min(prefix, suffix)
3. 투포인터로 풀어보기
   발상의 전환 → 꼭 면적을 높이(즉, 세로)를 기준으로 더할 필요 없음. 가로로 한 층 한 층 더해갈 수도 있다.

코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        int[] polls = new int[1010];
        int x, y;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            polls[x] = y;
        }

        int[] prefix = new int[1010];
        for (int i = 1; i < 1010; i++) {
            prefix[i] = Math.max(prefix[i - 1], polls[i]);
        }

        int[] suffix = new int[1010];
        for (int i = 1008; i >= 1; i--) {
            suffix[i] = Math.max(suffix[i + 1], polls[i]);
        }

        int sum = 0;
        for (int i = 0; i < 1010; i++) {
            sum += Math.min(prefix[i], suffix[i]);
        }

        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1912. 연속합

1912번: 연속합

문제 요약

• n개의 정수로 이루어진 임의의 수열
• 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합 구하기
  • 최소 한 개 이상 선택할 것

시간 제한

• 1초

입력

• n ( 1 ≤ n ≤ 10만)
• n개의 정수로 이루어진 수열
  • -1000~1000

출력

• 연속 부분 수열의 합계 중 최대값

접근법

for문을 딱 한 번만 써야 한다.

즉, 누적합 배열에서 모든 연속 부분 수열의 합계를 구한다해도 10만*10만 정도로 시간 초과가 발생할 수 있음

부분 수열 케이스

1. 각 원소 자체 ⇒ O(1) 가능
2. 해당 원소까지의 누적합 ⇒ O(1) 가능
3. 앞의 원소 일부를 제거한 부분 수열들 ⇒ 여기서 문제가 됨.
   그러나 이미 앞에서 지나간(?) 부분 수열에 다음 원소가 추가되는 느낌으로 생각해본다면,,,
   우리가 구하려는게 결국 최대값을 구하려는 거기 때문에, 뒤에 원소로 이동할 때 앞에 이미 구해진 일부 부분 수열합계 중 최대값이랑만 더하면 된다.
   다음과 같이 수열이 주어진다면
   

   10	-4	3	1	5	6	-35	12	21	-1
   10
   10	6
   10	6	9
   10	6	9	10
   10	6	9	10	15
   10	6	9	10	15	21
   10	6	9	10	15	21	-14
   10	6	9	10	15	21	-14	-2
   10	6	9	10	15	21	-14	-2	19
   10	6	9	10	15	21	-14	-2	19	18

   • arr[1] : 10
     • [10]
     • summax = 10
     • answer = 10
   • arr[2] : -4
     • [10, -4] : summax + -4 = 6
     • [-4] < 6
     • summax = 6
     • answer = 10
   • arr[3] : 3
     • [10, 3] : summax + 3 = 9
     • [-4, 3]
     • [3] < 9
     • summax = 9
     • answer = 10
   • arr[4] : 1
     • [10, 1] : summax + 1 = 10
     • [-4, 1]
     • [3, 1]
     • [1] < 10
     • summax = 10
     • answer = 10
   • arr[5] : 5
     • [10, 5] : summax + 5 = 15
     • [-4, 5]
     • [3, 5]
     • [1, 5]
     • [5] < 15
     • summax = 15
     • answer = 15
   • arr[6] : 6
     • [10, 6] : summax + 6 = 21
     • [-4, 6]
     • [3, 6]
     • [1, 6]
     • [5, 6]
     • [6] < 21
     • summax = 21
     • answer = 21
   • arr[7] : -35
     • [10, -35] : summax + -35 = -14
     • [-4, -35]
     • [3, -35]
     • [1, -35]
     • [5, -35]
     • [6, -35]
     • [-35] < -14
     • summax = -14
     • answer = 21
   • arr[8] : 12
     • [10, 12] : summax +12 = -2
     • [-4, 12]
     • [3, 12]
     • [1, 12]
     • [5, 12]
     • [6, 12]
     • [-35, 12]
     • [12] > -2
     • summax = 12
     • answer = 21
   • arr[9] : 21
     • [10, 21]
     • [-4, 21]
     • [3, 21]
     • [1, 21]
     • [5, 21]
     • [6, 21]
     • [-35, 21]
     • [12, 21] : summax + 21 = 33
     • [21] < 33
     • summax = 33
     • answer = 33
   • arr[10] : -1
     • [10, -1]
     • [-4, -1]
     • [3, -1]
     • [1, -1]
     • [5, -1]
     • [6, -1]
     • [-35, -1]
     • [12, -1] : summax + -1 = 32
     • [21, -1]
     • [-1] < 32
     • summax = 32
     • answer = 33
   따라서 33
   ⇒ 즉, 지금까지 나온 부분수열의 최적합이랑만 더하는 거다
   그래서 정답이 될 최종 최대값이랑, 부분수열 합계의 최대값 두 변수를 만들어서 쓰려고 한다.

코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        int answer = Integer.MIN_VALUE; // 정답(부분 수열의 최종 최대값)
        int sumMax = 0; // 부분 수열 합계 중 최대값
        int sum = 0; // sumMax와 배열의 원소 숫자와 더한 값
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());

            sum = sumMax + num;

            if(sum < num) sumMax = num;
            else sumMax = sum;

            if(answer < sumMax) answer = sumMax;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 14719. 빗물

14719번: 빗물

문제 요약

• 2차원 세계에서 고이는 빗물의 총량 구하기
  • 빗물은 블록 사이에 빗물이 고인

시간 제한

• 1초

입력

• 2차원 세계의 세로 길이 H, 가로 길이 W
  • (1 ≤ H, W ≤ 500)
• 블록이 쌓인 높이를 의미하는 0이상 H이하 정수가 맨 왼쪽 위치부터 차례대로 W개 주어짐

출력

• 한 칸의 용량은 1이라고 가정 할 때, 고이는 빗물의 총량 출력
• 전혀 고이지 않는다면 0 출력

접근법

1. 완전 탐색으로 생각하기
   • 예전에 비슷한 문제로 창고다각형이 생각나는뎅,,,
   • 블록 중 가장 높은 블록을 기준으로 좌, 우 구역으로 나눈다.
   • 좌측의 경우 → 방향으로 왼쪽부터 등장한 블록 중 가장 최대 높이 값을 기준으로 블록 높이 차만큼 빗물양을 더해주고
   • 우측의 경우 ← 방향으로 오른쪽부터 등장한 블록 중 가장 최대 높이 값을 기준으로 블록 높이 차만큼 빗물양을 더해준다.
   • 여기서 창고다각형이랑 다른점은 고인 빗물을 계산해야하므로,, 현재까지 최대값과 다음 블록의 높이차가 음수인 경우 더하지 않는다.
2. 최적화 하기
   • 사실 완탐으로 풀어도 충분히 가능한 문제지만 최적화를 통해 다른 방식으로 풀어보자!
   • 물이 고이는 상황
     • 최소 2개 이상의 블록이 있어야 하고,
     • 좌측, 우측 블록 사이에 빈 공간 또는 블록들이 있어야 하며, 해당 블록들은 좌측, 우측의 블록 높이보다 작아야 한다. ⇒ 뭔가 투포인터로도 풀 수 있을 것 같은데….???
   • 결국 완탐에서도 최대값이 기준이 되었다.
     • 가장 큰 높이를 기준으로 좌측, 우측으로 구역을 나눠서 진행하므로
     • 내 왼쪽에 최대값이 누구인지, 내 오른쪽에 최대값이 누구인지를 알아야 한다.
     • 각각 최대값 기록 배열 prefix, suffix를 만들어준다.
     • 최대값(min(prefix, suffix)) - 블록 높이가 양수인 경우만 더해준다.
   • 투 포인터로 풀어본다면

코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] blocks = new int[W + 2];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= W; i++) {
            blocks[i] = Integer.parseInt(st.nextToken());
        }

        int[] prefix = new int[W + 2];
        int[] suffix = new int[W + 2];
        for (int i = 1; i <= W; i++) {
            prefix[i] = Math.max(prefix[i - 1], blocks[i]);
        }
        for (int i = W; i >= 1; i--) {
            suffix[i] = Math.max(suffix[i + 1], blocks[i]);
        }

        int sum = 0, diff = 0;
        for (int i = 1; i <= W; i++) {
            diff = Math.min(prefix[i], suffix[i]) - blocks[i];
            if (diff > 0) {
                sum += diff;
            }
        }

        bw.write(String.valueOf(sum));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 3020. 개똥벌레

3020번: 개똥벌레

문제 요약

• 동굴 길이 N미터, 높이 H미터
• 종유석, 석순이 번갈아 등장
• 개똥벌레는 일직선으로 지나감
• 개똥벌레가 파괴해야 하는 장애물 최솟값과 그러한 구간이 총 몇 개 있는지 구하기

시간 제한

• 1초

입력

• N H (N은 항상 짝수)
  • 1≤N≤20만
  • 2≤H≤50만
• N개의 줄에 장애물 크기가 순서대로 주어짐
  • H보다 작은 양수

출력

• 개똥벌레가 파괴해야하는 장애물 최솟값과 그러한 구간의 수

접근법

1. 완전 탐색으로 생각하기
   • 종유석, 석순 번갈아 등장하므로 → ← 방향으로 번갈아 채워준다 생각
   • H크기의 배열을 하나 만들어서, 입력 받은 순서대로 크기만큼 0부터 오른쪽으로, H-1부터 왼쪽으로 이동하며 원소값을 +1한다.
     0 1 2 3 4 5 6
     1
           1 1 1 1 1
     2 1 2
                2 2 2
     3 2 3 2
                   3 3
   • 배열 원소 들 중 가장 최솟값을 찾고, 해당 값과 개수를 반환한다.
   • 그러나 N개가 20만개, H길이가 50만개까지 가능하므로 최악의 경우 20만 * 50만 까지 연산이 발생할 수 있어 시간초과 뜬다!
2. 최적화 하기
   • 입력마다 구간 업데이트를 진행
     • 1 → [0] +1, [1] -1
     • 5 → [H-1-4] +1, [H] -1
     • 3 → [0] +1, [3] -1
     • 3 → [H-1-2] +1, [H] -1
     • 5 → [0] +1, [5] -1
     • 1 → [H-1] +1, [H] -1
   • 그 다음 누적합 배열을 한번에 구하고, 그 중 최솟값을 찾는다.
     
     

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int H = Integer.parseInt(st.nextToken());

        int[] objects = new int[H + 2];
        int len;
        for (int i = 0; i < N; i++) {
            len = Integer.parseInt(br.readLine());
            if (i % 2 == 0) {
                // 석순
                objects[1] += 1;
                objects[len + 1] += -1;
            } else {
                // 종유석
                objects[H - len + 1] += 1;
                objects[H + 1] += -1;
            }
        }

        int answer = Integer.MAX_VALUE, cnt = 0;
        for (int i = 1; i <= H; i++) {
            objects[i] += objects[i-1];

            if (answer > objects[i]) {
                cnt = 1;
                answer = objects[i];
            } else if (answer == objects[i]) {
                cnt++;
            }
        }

        bw.write(answer + " " + cnt);
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1687. 행렬 찾기

1687번: 행렬 찾기

문제 요약

• 0과 1로 이루어진 행렬
• 부분행렬 = 이 행렬에 포함되는 행렬 의미
  • 이 중 0으로만 이루어진 부분 행렬 중 가장 면적이 큰 것 찾기

시간 제한

• 2초

입력

• 행렬 크기 N M (1≤N, M≤333)
• N개의 줄에 M개의 정수가 주어짐(행렬 원소값)

출력

• 답 출력

접근법

1. 완전 탐색으로 접근
   for문을 이용해서 (0,0)부터 (N-1,M-1)까지 start 포인트를 정하고, 일일이 부분행렬 찾기,, (사각형 모양 유지하며 찾기)
2. 최적화 하기
   합계가 0인 부분행렬을 찾는다.
   그러나 범위가 333까지 가능하니까 최적화를 해야함
   ⇒ (r2,c2)를 탐색하는 과정에서 합계가 0이 아닌 지점을 찾게되면 다음부터는 해당 c2보다 작은 곳만 탐색을 해야한다..

코드

• split를 써서 string 배열을 사용하니까 메모리 초과가 떴다.
• 되도록 사용을 지양하자!!!

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N + 1][M + 1];
        String str;
        for (int i = 1; i <= N; i++) {
            str = br.readLine();
            for (int j = 1; j <= M; j++) {
                arr[i][j] = str.charAt(j - 1) - '0';
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
            }
        }

        int answer = 0, range = M;
        for (int r1 = 1; r1 <= N; r1++) {
            for (int c1 = 1; c1 <= M; c1++) {

                if (arr[r1][c1] - arr[r1 - 1][c1] - arr[r1][c1 - 1] + arr[r1 - 1][c1 - 1] == 1) {
                    continue;
                }

                range = M;
                for (int r2 = r1; r2 <= N; r2++) {
                    for (int c2 = c1; c2 <= range; c2++) {

                        if (arr[r2][c2] - arr[r1 - 1][c2] - arr[r2][c1 - 1] + arr[r1 - 1][c1 - 1] == 0) {
                            answer = Math.max(answer, (r2 - r1 + 1) * (c2 - c1 + 1));
                        } else {
                            range = c2 - 1;
                        }
                    }
                }
            }
        }


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2015. 수들의 합 4

2015번: 수들의 합 4

문제 요약

• 배열의 부분합 중 합이 K인 것이 몇 개?

시간 제한

• 2초

입력

• N K
  • 1 ≤ N ≤ 20만
  • -20억 ≤ K ≤ 20억
• 배열의 원소 N개
  • -10,000 ≤ 원소 ≤ 10,000

출력

• 합이 K인 부분합의 개수?

접근법

1. 완전 탐색으로 접근
   배열의 누적합을 구하고, 2중 for문으로 부분합들 중에 합이 K인 것을 찾는다. ⇒ 20만=20만 ⇒ 시간초과
2. 최적화 하기
   for문 하나만 사용해야 함.
   1 2 3 4 5 0 ( k = 5 )
   1
   1 3
   1 3 6
   1 3 6 10
   1 3 6 10 15
   1 3 6 10 15 15 → 앞의 값을 뺄 때 5가 나오는 개수를 구할 것
   cnt배열을 만들어서 cnt[prefix[i] - k]만큼 답에 더해주고, cnt[prefix[i]]++을 해주면 된다.
   문제는 k가 -20억~20억이 가능하기 때문에 해당 크기를 담을 수 있는 배열을 만들 수 없다는 것.
   배열 대신 Map을 사용해서 <idx, value> = <number, cnt>를 사용하자!

코드

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        Map<Long, Long> cntMap = new TreeMap<>();
        cntMap.put(0L, 1L);
        long ans = 0;
        for (int i = 1; i <= N; i++) {
            if(cntMap.containsKey(prefix[i]-K)) ans += cntMap.get(prefix[i]-K);

            if(cntMap.containsKey(prefix[i])) cntMap.replace(prefix[i], cntMap.get(prefix[i])+1);
            else cntMap.put(prefix[i], 1L);
        }

        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
        br.close();
    }
}