[백준] 1806 부분합 - 자바

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

1806번: 부분합

문제 풀이

투 포인터를 활용해 연속된 구간의 부분합이 S이상인 구간 중 최소 길이를 구하는 문제이다.

두 포인터(start, end) 모두 0번 인덱스부터 시작하여 S이상을 만족하는 구간을 찾는다. 찾는 방법은 다음과 같다.

sum: start~end 합 이라고 할 때

1.  sum >= S
   • 기존 start가 갖고 있던 값을 sum에서 뺀 후 start를 증가시켜 범위를 줄인다 
2. sum < S
   • S를 만족할 때까지 end를 증가시켜 증가된 부분의 합을 sum에 축적

 

그렇다면 종료조건은 어떻게 될까? 사실 이 부분이 제일 헷갈렸다

while 조건문부터 확인해보면 다음과 같다.

int[] nums = new int[N + 1];
for (int i = 0; i < N + 1; i++) {
    nums[i] = Integer.parseInt(st.nextToken());
}

while (start <= end && end <= N) {
    if (sum < S) {
        sum += nums[end];
        end++;
    }
    if (sum >= S) {
        sum -= nums[start];
        start++;

        len = Math.min(len, end - start + 1);
    }
}

while 조건 1) start <= end

start가 end보다 커졌다는 거는 start=end가 같고 sum>=S인 상황이다. 즉, 이미 S이상이어야 한다는 조건이 성립인데 start=end이므로 길이가 1이다. 이보다 더 작은 부분합은 있을 수 없다. 따라서 불필요한 연산을 생략할 수 있다.

 

while 조건 2) end <= N

초기화 코드를 보면 크기를 0~N범위의 N+1개만큼 설정하고 정작 사용하는 값은 0부터 N-1까지 N개를 지정해주는 것을 볼 수 있다.

만약 크기를 0~N범위 N+1개가 아닌 0~N-1의 N개를 설정했다고 가정해보자. 

4 100
1 2 3 101

// N=4, S=100, nums[0~3]

다음 입력값이 들어올 때 end는 101인 start=0, end=3이 돼서야 S를 만족할 것이고 그 후에 start를 늘려가며 범위를 줄여나갈 것이다 (while문에 의해서). 하지만 end<N으로 해버리면 end가 3이 됐을 때 101을 더하고 end가 증가하여 4가 된다. 이후 start를 증가시켜 범위를 감소 시키는 로직이 실행되어야 하지만 end=4가 돼버리면서 while문을 벗어나버리게 된다.

따라서 int 배열의 크기를 일부러 1 증가시켜 N+1만큼 선언 하고 사용하지 않는 인덱스로 남겨두어야 한다. 값을 지정하지 않으면 자동으로 0으로 초기화 돼고 0은 부분합의 변화를 주지 않기 때문에 구하고자 하는 결과값에도 영향을 주지 않는다.

 

정리해 부분합 범위의 end가 마지막 인덱스를 가지기 위해서 nums의 배열을 하나 증가시켜줘야 한다.

코드

package 백준;

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

public class b1806 {
    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());
        
        st = new StringTokenizer(br.readLine());
        int[] nums = new int[N + 1]; // 0~N-1 인덱스만 사용하지만 배열은 0~N까지 존재해야 함
        for (int i = 0; i < N + 1; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int start = 0, end = 0;
        int sum = 0;
        int len = Integer.MAX_VALUE;
        // 조건문 설명은 블로그 글 참고
        while (start <= end && end <= N) {
            if (sum < S) {
                sum += nums[end];
                end++;
            }
            if (sum >= S) {
                sum -= nums[start];
                start++;

                len = Math.min(len, end - start + 1);
            }
        }
        
        System.out.println(len == Integer.MAX_VALUE ? 0 : len);
    }
}