[백준] 1806번 부분합

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   길이가 N인 수열에서 연속된 수들의 부분합 중 그 합이 S 이상이 되며 가장 짧은 것의 길이를 구하는 문제이다. 첫째 줄에 N, S가 주어지고 둘째 줄에 공백으로 각 원소를 구분하는 수열이 주어진다. 제한 사항은 다음과 같다.

 

• 10 ≤ N < 100,000
• 1 ≤ S ≤ 100,000,000
• 1 ≤ 수열의 각 원소 ≤ 10,000
• S 이상이 불가능한 경우 0 출력

 

 

---

접근 방식

   투 포인터의 개념을 이용해 문제를 해결하였다. 해당 문제에선 합에 추가할 인덱스의 위치를 head, 합에서 제거할 인덱스의 위치를 tail이라 정의하였다. 길이에 대한 탐색 과정을 예시와 함께 알아보자.

 

 

   배열의 첫번째 인덱스는 시작 지점으로 사용하기 위해 추가한 인덱스로 실제 입력받은 배열은 1로 채워진 공간들이다. tail은 0번 인덱스부터, head는 1번 인덱스부터 시작한다. total은 현재 파란색 범위에 해당하는 구간의 합이다.

   이 다음 진행과정에 대해 이해해보자. 기준 합인 S보다 현재 total의 값이 작기 때문에 head를 증가시켜야 한다.

 

 

   total이 S와 같거나 큰 경우 해당 부분합은 유효하기 때문에 len을 갱신해주어야 한다. 이때 len은 head - tail을 이용해 쉽게 구할 수 있다. len에 대한 갱신이 끝났으면 이제 tail을 증가시키며 len의 크기를 줄일 수 있는지 확인해야 한다. 예제에서 볼 수 있듯이 head를 통해 추가된 값에 의해 total의 값이 매우 커져 tail에 위치한 값을 제거해도 total이 S보다 충분히 큰 경우가 존재하기 때문이다. 예제의 이후 과정을 확인해보자.

 

 

   최종적으로 head가 배열의 범위를 벗어나고 total의 값이 S보다 작아진 경우에 해당 반복과정이 종료된다. 중간에 total이 조건을 만족하는 경우가 많았지만 len의 최소를 구하는 문제이기 때문에 초반에 1로 초기화된 이후 변하지 않는 것도 확인할 수 있다.

---

코드

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

public class 백준1806번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        token = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(token.nextToken());
        int S = Integer.parseInt(token.nextToken());
        //수열을 저장할 배열에 크기를 1 증가시켜 시작 지점으로 활용
        int[] numbers = new int[N + 1];

        token = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++)
            numbers[i] = Integer.parseInt(token.nextToken());

        //head 합에 추가할 인덱스 위치
        //tail 합에서 제거할 인덱스 위치
        //total 현재 합
        int head = 1, tail = 0, total = 0, len = N + 1;
        
        while (!(head == N + 1 && total < S)) {
            if (total >= S) {
                //현재 합이 S보다 크거나 같은 경우, 더 작은 len를 저장
                //tail 위치의 값을 합에서 제거 및 tail 위치 이동
                len = Math.min(len, head - tail);
                total -= numbers[tail];
                tail++;
            } else {
                //현재 합이 S보다 작은 경우, head 위치의 값을 합에 추가 및 head 위치 이동
                total += numbers[head];
                head++;
            }
        }

        //S보다 크거나 같은 합을 구할 수 없는 경우 len을 0으로 초기화
        if (len == N + 1)
            len = 0;
        System.out.println(len);
    }
}