구간 합 구하기(JAVA)

구간 합 구하기는 원하는 구간의 합을 구하기 위해 미리 구간들의 합을 계산해 배열 상태로 저장해 놓는 것이다.

 

구간 합 구하기 예제 1(11659번)

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

이 문제는 수의 개수 N과 퀴리의 개수 M이 주어지고 배열의 숫자가 주어지면 구간합을 구하는 문제이다.

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

public class Main {
    public static void main(String[] args) throws IOException {
    	//많은 수를 빠르게 얻기 위해 Scanner 대신 BufferedReader를 사용한다.
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer는 받은 문자열을 하나씩 나눈다.
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int n= Integer.parseInt(stringTokenizer.nextToken());
        int m = Integer.parseInt(stringTokenizer.nextToken());
        long[] s = new long[n+1];  //합을 계산할 구간 합 배열
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 1; i <= n; i++) {
        	//구간 합 구하기
            s[i] = s[i - 1] + Integer.parseInt(stringTokenizer.nextToken());
        }
        for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int u = Integer.parseInt(stringTokenizer.nextToken());
            int v = Integer.parseInt(stringTokenizer.nextToken());
            System.out.println(s[v]- s[u-1]);
        }
    }
}

자바는 C++보당 상당히 느리고 양이 크다. 제일 처음 Scanner로 풀었을 때는 걸린 시간이 2배다.

 

구간 합 구하기 예제 2(11660)

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

1차원 배열에서 구하던 구간 합을 2차원에서 구하는 것이다.

0	0	0	0	0
0	1	2	3	4
0	2	3	4	5
0	3	4	5	6
0	4	5	6	7

예시 배열이다. 이 것을 구간 합 배열로 바꾸면 된다.

0	0	0	0	0
0	1	3	6	10
0	3	8	15	24
0	6	15	27	42
0	10	24	42	64

 처음 행과 열이 1인 곳은 일차원 배열에서 했던 것처럼 저번 꺼를 지금에 더해준다.

 for (int i = 2; i <= n; i++) {
            sum[1][i] = arr[1][i] + sum[1][i-1];
            sum[i][1] = arr[i][1] + sum[i-1][1];
        }

이제 2번째 행과 열부터 계산을 해줘야 한다. 이때는 1,1 부터 현재까지 모두 더한 값을 구해 준다고 생각하면 된다.

위 그림처럼 (3,3)을 구한다고 할 때, (3,2)까지 합과 (2,3)까지 합을 더한다. 그렇게 되면 (2,2)까지 합을 한번더 더하므로 이것을 빼준다. 그 뒤 (3,3)의 숫자를 더하면 (1,1) 부터 (3,3) 까지의 합이다.

 for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= n; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j];
            }
        }

위 그림은 (2,2) 에서 (4,4) 까지의 합을 구한다고 할 때, (1,1) 부터 (4,4) 까지의 합중 빼야 하는 요소이다. 

(2,2)의 전 행과 열인 첫번째 행과 열은 빼주고 (1,1)은 2번 빼줬으므로 한번 더해준다.

 for (int i = 0; i < m; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int u1 = Integer.parseInt(stringTokenizer.nextToken());
            int v1 = Integer.parseInt(stringTokenizer.nextToken());
            int u2 = Integer.parseInt(stringTokenizer.nextToken());
            int v2 = Integer.parseInt(stringTokenizer.nextToken());
            int res = sum[u2][v2] - sum[u1-1][v2] - sum[u2][v1-1] + sum[u1-1][v1-1];
            System.out.println(res);
	}

전체 코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_11660.java

GitHub - Heron-Woong/CodingTest_Practice

 

구간 합 구하기 예제 3(10986)

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

이 문제는 두 번째 줄에 주어지는 수열의 부분 합이 M으로 나누어지는 총 갯수를 구하는 것이다.

 

문제에 대한 아이디어

A+B를 C로 나눈 나머지는 (A%C+B%C)%C와 일치한다. 각각의 구간 합 배열을 만들고 구간 합을 M으로 나누면 각각 나머지를 알 수 있다.

1

2

3

1

2

구간 합 배열로 만들면

1

3

6

7

9

 이제 이것을 각각 M = 3으로 나눈다.

1

0

0

1

0

여기서 0이라는 것은 거기까지 구간 합이 M으로 나누어진 다는 것이다. 그러므로 count에 3을 더한다. 이제 나머지가 같은 부분을 살펴봐야 한다. 나머지가 같은 두 수를 빼고 다시 3으로 나누면 나머지는 0이 된다. 

3x + 1 - 3y -1 = 3x - 3y = 3(x-y) 이므로 3으로 나누어 떨어진다. 그러므로 나머지 같은 수 중 2개를 뽑는 경우의 수를 카운트에 더해주면 된다. 즉, 3 C 2 + 2 C 2 + 3 = 7이다.    

 

구현

구간 합 배열 만들기

long sum[] = new long[n];
sum[0] = sc.nextInt();
for (int i = 1; i < n; i++) {
    sum[i] = sum[i-1] + sc.nextInt();
}

각 인덱스에 수의 나머지를 구하고 나머지가 0 과 같으면 count해준다. 나머지가 0이 아니면 다른 나머지는 몇개가 나왔는지 구한다.

long reminder[] = new long[m];
for (int i = 0; i < n; i++) {
    rem = (int)(sum[i]%m);
    if(rem == 0) {
        res++;
    }
    reminder[rem]++;
}

같은 나머지중 2개씩 고르는 count를 샌다.

for (int i = 0; i < m; i++) {
    if(reminder[i] > 1){
        res = res + (reminder[i] *(reminder[i]-1) /2);
    }
}

 

최종 코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_10986.java

GitHub - Heron-Woong/CodingTest_Practice