BOJ | Gold 4/1806/부분합

1. 문제 이해

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력값이 길이가 N인 수열에 해당한다. 이 수열의 부분합을 구하는데, 또다른 입력 값인 S 이상이 되는 경우를 찾는다. 그 중에서 연속된 수의 길이 중 가장 짧은 길이를 구하는 것이다. 이때 부분합을 구하는 방법으로는 1차원 배열이므로 투포인터 알고리즘을 적용한다. 

[그림 1] 수열

[그림 2] 두 포인터

* 투포인터(Two Pointer) 알고리즘 : left와 right로 구분한 두 포인터를 좌우로 이동해가면서 요구조건에 맞는 답을 찾는 풀이법이다.

[그림 3] 두 포인터 와 배열

2. 로직

2-1) 로직 플로우

정수 배열은 수열의 길이는 N+1로 초기화 시킴(right의 index 때문, [그림 3] 참고). 정수배열로 입력 받을 때 입력받은 수열 전체의 합이 S이상이 되는 경우를 체크하기 위해 total 변수를 생성하고, total에 입력받은 값들을 누적시킨다. 그리고 두 개의 포인터를 사용하여 탐색하는 로직 직전, 입력받은 값들과 S가 일치하는지를 확인한다. 그리고 두 개의 포인터를 left, right로 지정하여 0으로 초기화 시킨 total에 누적시킨다. 이때  left와 right의 차이로 수열 길이의 최솟값을 구하고, 최솟값을 구하기 위해 모든 위치를 탐색해야한다. 그래서 누적합이 S보다 크거나 같으면  left를 증가시켜서 누적합에서 빼주고, 그렇지 않으면 right를 증가시키고 total에서 그 위치의 요소를 더한다.

2-2) 로직 상세

1) 입력 받은 데이터를 통해 수열을 저장하는 길이가 N+1인 배열을 생성 후 그 배열에 수열의 각 요소를 할당함

2) 입력 받는 동시에 수열의 전체 합(total)을 구하고, 입력이 끝난 뒤 S와 일치하는지를 확인

3) total을 0으로 초기화시킴, left는 0으로 초기화 시킴, right는 수열의 길이-1로 초기화 시킴, 수열의 길이 최솟값을 구할 min은 Integer.MAX_VALUE로 초기화함.

4) 두 포인터를 사용하여 누적합의 길이를 구하는 로직에 통과시킴. 

5) 누적합이 S보다 크거나 같은 경우 left와 right의 차이를 min에 할당.

6) 누적합이 S보다 크면 left를 증가시킨 뒤 누적합에서 빼주고, 그렇지 않으면 right를 증가시켜 total에 그 위치의 요소를 누적합에 더함.

7) left와 right가 수열의 길이가 될 때까지 탐색을 반복.

8) min값이 초기화시킨 Integer.MAX_VALUE인지를 비교하여 true면 "0"을 출력 시키고, 그렇지 않으면 수열의 최솟값을 출력시킴.
 

3. 구현

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 {
        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[n+1];
        int total = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
            total += nums[i];
        }

        if(total == s) System.out.println(nums.length-1);
        else {
            int min = Integer.MAX_VALUE;
            int left = 0;
            int right = 0;
            total = 0;
            while (left <= n && right <= n) {
                if (total >= s && min > right - left) {
                    min = right - left;
                }

                if (total >= s) total -= nums[left++];
                else total += nums[right++];
            }

            if(min == Integer.MAX_VALUE) System.out.println("0");
            else System.out.println(min);
        }
    }
}

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

1806번: 부분합

직접 문제를 풀어봄으로써 위 내용을 확인하셨으면 좋겠습니다. 감사합니다 :)