[알고리즘 / 백준] 1806 - 부분합

www.acmicpc.net/problem/1806

1806번: 부분합

 

문제는 위와 같으며, 연속된 수들의 부분합 중에 주어지는 S 보다 큰 값을 이루는 수의 최소 개수를 구하는 문제였습니다. 처음에는 이 문제를 배열로 만들고 각 인덱스 개수만큼 수를 더해가면서 배열의 값을 뒤로 이동시키는 방식으로 풀었는데 시간 초과가 발생하였습니다...ㅠㅠ

 

그래서 이 문제를 low, high 두개의 인덱스 값을 포인트로 두어 두 값을 이동시키는 방식으로 해결하였습니다.

 

두 포인터를 주어진 수열이 끝날 때까지 이동시키는데

 

1. low와 high 사이 수의 합이 S보다 작은 경우

: high 포인트를 한칸 뒤로 이동시키고 그 위치의 값을 더합니다.

 

2. low와 high 사이 수의 합이 S와 같은 경우

: 부분합의 개수 중 작은 값을 result 변수에 저장합니다. (부분합의 개수는 high - low + 1 입니다.) 그런 다음, high 를 다음 위치로 옮기고 그 값을 더합니다.

 

3. low와 high 사이 수의 합이 S보다 큰 경우

: 부분합의 개수 중 작은 값을 result 변수에 저장합니다. (부분합의 개수는 high - low + 1 입니다.) 그런 다음, low 값을 부분합에서 빼주고 low 의 위치를 한칸 뒤로 이동시킵니다.

 

예제를 통해 위 경우들을 살펴보겠습니다.

 

초기 상태는 아래와 같습니다.

 

sum이 5로 S인 15보다 작기 때문에, high를 한칸 뒤로 옮기고 그 값을 sum에 더해줍니다.

 

아직도 sum이 작기 때문에 위와 같은 과정을 계속 진행하면서, sum이 S이상일 때까지 반복합니다.

 

sum이 S보다 커지게 되면, 부분합의 개수를 구합니다. high - low + 1 = 4 - 0 + 1 = 5 입니다. 그런 다음, low 위치의 값을 sum에서 빼고 low를 한칸 뒤로 이동시킵니다.

 

여전히 sum의 값이 S보다 크기 때문에 위에서 진행한 과정을 sum이 S보다 작거나 같을 때까지 반복합니다.

 

sum이 S와 같은 경우, 부분합의 개수를 구합니다. high - low + 1 = 4 - 3 + 1 = 2 입니다. 이 부분합의 개수가 전에 구했던 부분합의 개수(5)보다 작은 경우에 값을 교체합니다. 이후, high를 한칸 뒤로 이동시키고 그 값을 더해줍니다. 이후 주어진 수열이 끝날 때까지 위 과정들을 반복합니다.

---

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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

        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        int[] nums = new int[100000];
        int[] tmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        for (int i = 0; i < n; i++) {
            nums[i] = tmp[i];
        }

        int low = 0, high = 0;
        int sum = nums[0];
        int result = 100001;

        // 수열을 하나씩 돌면서 끝까지 확인
        while (low <= high && high < n) {
            // 부분합이 s보다 작은 경우
            if (sum < s) {
                // high 포인터를 한칸 이동시키고 그 위치의 값을 부분합에 추가
                sum += nums[++high];
            } else if (sum == s) {  // 부분합이 s와 같은 경우
                // 지금까지 구한 부분합의 개수를 저장 (기존 부분합의 개수와 비교하여 더 작은 값을 저장)
                result = Math.min(result, high - low + 1);
                // high 포인터를 한칸 이동시키고 그 위치의 값을 부분합에 추가
                sum += nums[++high];
            } else if (sum > s) {  // 부분합이 s보다 큰 경우
                // 지금까지 구한 부분합의 개수를 저장 (기존 부분합의 개수와 비교하여 더 작은 값을 저장)
                result = Math.min(result, high - low + 1);
                // low 위치의 값을 부분합에서 빼주고 low 포인터를 한칸 이동
                sum -= nums[low++];
            }
        }

        // 부분합이 s 이상이 아닌 경우 결과를 0으로 초기화
        if (result == 100001) {
            result = 0;
        }

        System.out.println(result);
    }
}