[Baekjoon] 1806번: 부분합

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

1806번: 부분합

문제 설명

10,000 이하 자연수로 이루어진 길이 N의 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구하는 프로그램을 작성해야 한다. 만약 합이 없다면 0을 출력한다.

풀이 방법 - 투 포인터

이 문제는 투 포인터를 활용하여 해결할 수 있다. 예제 입력을 가지고 과정을 살펴보자.

 

준비

• N = 수열의 길이이다.
• S = 비교대상이 될 합이다.
• SUM = 부분합을 저장하기 위한 변수이다.
• L = 왼쪽 포인터 변수이다.
• R = 오른쪽 포인터 변수이다.

 

먼저 L과 R을 같은 위치에 놓은 후 R을 증가시키면서 부분합을 구해나간다.

1회전

2회전

이런 식으로 SUM이 S보다 같거나 커질 때까지 R을 증가시키며 더해나간다.

5회전

5회전 후에 SUM이 S보다 커졌다. 그렇다면 현재 범위는 R - L로 구할 수 있으며 5가 된다. 따라서 최솟값을 5로 변경한다.

그 후엔 L에 위치한 값을 빼나간다. 이렇게 하면서 부분합의 범위를 줄여나가는 것이다.

SUM이 S보다 작아지면 다시 R을 증가시키면서 더해나간다.

이런 식으로 L과 R이라는 두 포인터 변수의 위치를 변경해나가면서 부분합의 최소 범위를 구한다.

맨 마지막에 0이라는 추가 공간을 둔 이유는 위 과정을 보면 알다시피 R이 가리키는 인덱스 바로 이전까지의 합을 구하기 때문에 마지막 인덱스까지 계산을 하려면 공간이 한 칸 더 필요하기 때문이다.

코드는 다음과 같다.

import java.io.*;

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

        String[] split = br.readLine().split(" ");

        int N = Integer.parseInt(split[0]);
        int S = Integer.parseInt(split[1]);

        int[] nums = new int[N + 1];
        split = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(split[i]);
        }

        int left = 0, right = 0;

        int MAX = 100_000;
        int MIN = MAX;
        int sum = 0;

        while (left <= N && right <= N) {
            if (sum >= S && MIN > right - left)
                MIN = right - left;

            if (sum < S)
                sum += nums[right++];
            else
                sum -= nums[left++];
        }

        System.out.print(MIN == MAX ? 0 : MIN);
    }
}

실패한 풀이 방법. 이중 반복문 - 시간 초과

왼쪽에서부터 차례대로 모든 합을 구하도록 이중 반복문을 통해 구현했다. 하지만 시간 초과가 발생했다.

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

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

        String[] split = br.readLine().split(" ");

        int N = Integer.parseInt(split[0]);
        int S = Integer.parseInt(split[1]);

        int[] nums = 
            Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int left = 0;

        int MAX = 100_000;
        int MIN = MAX;
        int sum = 0;

        while (left < N) {
            for (int right = left; right < N; right++) {
                sum += nums[right];
                if (sum >= S) {
                    MIN = Math.min(MIN, (right - left + 1));
                    break;
                }
            }
            left++;
            if (MIN == 1)
                break; // 1보다 작은 경우는 없으므로
            sum = 0;
        }

        System.out.print(MIN == MAX ? 0 : MIN);
    }
}