[백준 - 1806] 부분합 - Java

문제 설명

 

1806번: 부분합

 

접근 방법

해당 문제는 누적합을 이용하여 해결할 수 있었습니다.

 

사실 처음 문제에 접근했을 때는 누적합을 생각하지 못하고 주어진 수열 상의 구간 길이 1부터 구간 길이 N까지의 부분합을 일일이 구해주면서 S 이상인 최소 구간을 구하도록 했었습니다. (결과는 당연히 시간 초과..😂) 이러한 방식은 반복문을 3개나 타기 때문에 매우 비효율적인 방법이었습니다. (반복문 하나는 구간 길이를 1부터 N까지 증가시키는 반복문, 다른 하나는 구간을 이동시키는 반복문, 또 다른 하나는 그 구간 내에 합을 일일이 구하는 반복문)

 

    // ...
        int windowSize = 1;
        int sum;
        while (true) {
            for (int i = 0; i < n - windowSize + 1; i++) {
                sum = getRestSum(i, i + windowSize);
                if (sum >= s) {
                    System.out.println(windowSize);
                    return;
                }
            }
            windowSize++;
            if (windowSize > n) {
                System.out.println(0);
                return;
            }
        }
    }

    private static int getRestSum(int start, int end) {
        int restSum = 0;
        for (int i = start; i < end; i++) {
            restSum += numbers[i];
        }

        return restSum;
    }

 

이때 누적합을 활용함으로써 구간 내에 합을 일일이 구해주는 반복문 없이 구간만 이동시켜줌으로써 각 구간의 합을 손쉽게 구할 수 있었습니다.

 

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

 

위 코드를 보면 처음 수열 데이터를 입력받을 때 이전 값들을 누적해서 더해주는 것을 확인할 수 있습니다.

 

        int windowSize = 1;
        int sum;
        while (true) {
            for (int i = n - 1; i - windowSize > -1; i--) {
                sum = numbers[i] - numbers[i - windowSize];
                if (sum >= s) {
                    System.out.println(windowSize);
                    return;
                }
            }
            if (numbers[windowSize - 1] >= s) {
                System.out.println(windowSize);
                return;
            }
            windowSize++;
            if (windowSize > n) {
                System.out.println(0);
                return;
            }
        }

 

위 코드와 같이 이후에는 누적하여 더해준 배열을 이용하여 구간만 이동시키면서 해당 구간의 부분합을 구할 수 있었고 이를 s(목표 값) 값과 비교해줄 수 있었습니다. 하지만 아직도 반복문을 통해 구간을 1부터 N까지 일일이 증가시키고 있고 주어진 수열 상에서 구간을 일일이 이동시켜가면서 s 값과 비교하고 있기 때문에 아직도 비효율적이었습니다. (아직도 제출 결과는 시간 초과 발생)

 

조금 더 효율적으로 반복문을 탈 수 있는 방법은 없을까 고민하던 중 for i for i + 1 반복문으로 해보면 어떨까 했습니다. 최초 누적합 배열의 첫 번째 요소를 하나의 지점(pointer)으로 잡고 그 이후에 요소들을 하나하나 지점으로 잡으면서 부분합을 구한 후 s와 비교하도록 했습니다.

 

이때 중요한 것은 for i + 1 반복문의 한 번의 루프로 수열의 구간의 길이 1부터 N까지의 부분합을 순서대로 모두 s와 비교할 수 있기 때문에 중간에 s 보다 크다면 그 구간의 길이를 정답으로 반환하면 됩니다. 이전 풀이와 같이 두 번의 반복문을 타긴했지만 이를 통해 좀 더 적은 탐색으로 정답에 접근할 수 있었습니다.

 

        int pointer, sum, result = 100000;
        boolean flag = true;
        for (int i = 0; i < n; i++) {
            pointer = numbers[i];
            if (pointer >= s) {
                result = Math.min(result, i + 1);
                flag = false;
            }
            for (int j = i + 1; j < n; j++) {
                sum = numbers[j] - pointer;
                if (sum >= s) {
                    result = Math.min(result, j - i);
                    flag = false;
                    break;
                }
            }
        }

 

전체 소스 코드

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

import java.util.StringTokenizer;

class Main {

    static int[] numbers;

    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()), s = Integer.parseInt(st.nextToken());
        numbers = new int[n];

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

        int pointer, sum, result = 100000;
        boolean flag = true;
        for (int i = 0; i < n; i++) {
            pointer = numbers[i];
            if (pointer >= s) {
                result = Math.min(result, i + 1);
                flag = false;
            }
            for (int j = i + 1; j < n; j++) {
                sum = numbers[j] - pointer;
                if (sum >= s) {
                    result = Math.min(result, j - i);
                    flag = false;
                    break;
                }
            }
        }

        if (flag) {
            System.out.println(0);
            return;
        }

        System.out.println(result);
    }
}

 

참고 자료

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