[Code Tree] 누적합 - 부분 수열의 합이 K 구하기

 

부분 수열의 합을 구할땐 누적합을 이용해서 푸는것도 좋은 방법이라고 생각하는 문제다.

 

n개의 정수로 이루어진 수열에서 연속된 구간의 합을 구하려합니다.

모든 연속된 구간의 합 중에서 합이 k인 것의 개수를 구하는 프로그램을 작성하세요.

첫 번째 줄에 정수 n과 k가 공백을 두고 주어집니다.

두 번째 줄에 n개의 정수가 공백을 두고 주어집니다.

3 ≤ n ≤ 1,000

1 ≤ k ≤ 1,000,000

1 ≤ 주어진 정수의 값 ≤ 1,000,000

시간 제한: 1000ms
메모리 제한: 80MB

 

먼저 든 생각은 아마 나이브한 생각이 아닐까 든다. 

 

모든 연속된 구간의 합중에서 합이  K인것을 먼저 찾아야한다. 문제를 해결하기위해선 

 

n의 범위가 1000이기에 n^2을 적용해야한다고 생각했다. k는 1000000 이였고, 메모리 제한도 괜찮아서 배열로 푸는게 좋다고 생각했다. 

 

첫번째 for문에선 index 0부터 시작하고 두번째 for문에선 index는 i부터 시작해야한다고 생각했다.

 

for문을 돌며 0부터 N, 1부터 N, 2부터 N까지 합을 더해 K인수를 찾는게 어떨까 생각해보았다. 

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

public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[] arr = new int[N];



        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int result=0;
        for(int i=0; i<N; i++){
            int count=0;
            for(int j=i; j<N; j++){
                count+=arr[j];
                if(count==M){
                    result++;
                }
            }
        }


        System.out.println(result);
        // 여기에 코드를 작성해주세요.
    }
}

 

이것은 내가생각했을때 되게 나이브한 풀이라고 생각한다. 하지만 누적합을 이용해서 푸는 풀이도 있다. 지금 같은 경우에는 시간복잡도가 굉장히 크기때문에 단순 2중 for문으로 해결이라고 생각한다 (저  방법또한 투포인터라고 생각해도 될거같다)

누적합을 이용해도 문제가 풀릴것 같았다. 

 

해당 arr 배열에서 prefixSum 배열을 만들어 이전에 있던값들을 모두 더하는 방법을 채택했다. 그리고 난뒤, 2중 for문을 사용하여 i부터 j까지의 누적합을 고려하여 K라면 count를 증가해 result의 값으로 출력해주었다. 

ex. 1~3합 => prefixsum[3]-prefixsum[0] 

ex. 7~10합 => prefixsum[10]-prefixsum[6]

 

 

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

public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        int[] arr = new int[N+1];
        int[] prefix = new int[N+1];
        

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

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

        int count=0;
        for(int i=1; i<=N; i++){
            for(int j=i; j<=N; j++){
                if(prefix[j]-prefix[i-1]==M){
                    count++;
                }
            }
        }
        System.out.println(count);
        // 여기에 코드를 작성해주세요.
    }
}

 

앞으론 부분 수열의합이 존재할때 다른 방법도 좋지만 누적합도 고려해보는 편이 좋을거같다.