[백준/Java] 1806 부분합

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

문제 요약

10,000 이하의 자연수로 구성된, 길이 N의 수열이 주어진다.
수열의 연속된 수의 부분합이 S 이상이 되는 것 중 가장 짧은 것의 길이를 구하자.
이때 N은 최대 10만, S는 최대 1억이다.

---

문제 접근

이 문제는 투포인터를 사용해서 해결할 수 있다.
투포인터는 크게 양쪽 끝에서 시작해 중간에서 만나는 방식이 있고, 한쪽 끝에서 같이 시작해 다른 속도로 진행하는 방식이 있는데, 이 문제는 후자의 방식으로 접근해야 한다.

1. right가 이동하면서 left와 right 사이의 합을 구한다.
2. 그 합이 S 이상이라면 left가 이동하면서 S 이상이 유지되는 가장 짧은 경우를 기록한다.
3. S가 유지되지 않는 경우에서 다시 right가 이동한다.
4. 이를 right가 끝에 도달하고, left가 이동해서 S가 얻어지지 않을 때까지 반복한다.

---

풀이

기본적인 아이디어는 다음과 같다.

1. (정리 예정)

이를 구현한 코드는 다음과 같다.

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

public class Main{
    static int N, S;
    static int[] arr;
    static ArrayList<Integer> lengths = new ArrayList<>();
    
    public static void getInput() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        		
        arr = new int[N];
        
        StringTokenizer nums = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
        	arr[i] = Integer.parseInt(nums.nextToken());
        }
    }

    public static long calSum(int leftIdx, int rightIdx) {
    	long sum = 0;
    	
    	for (int i = leftIdx; i <= rightIdx; i++) {
    		sum += arr[i];
    	}
    	
    	return sum;
    }
    
    public static boolean isPossible() {
    	if (calSum(0, N-1) >= S) {
    		return true;
    	}
    	return false;
    }
    
    public static void findMinLen() {
    	int leftIdx = 0;
    	int rightIdx = 0;
    	
    	int sum = arr[0];
    	
    	while (rightIdx < N-1) {
    		if (sum < S) {
    			rightIdx += 1;
    			sum += arr[rightIdx];
    		}
    		else if (sum >= S) {
    			// sum이 S보다 작을 때까지 반복
    			while (sum >= S) {
    				// 값 하나가 S 이상이라면 길이 1이 무조건 최소 길이다.
        			if (leftIdx == rightIdx) {
        				lengths.add(1);
        				return;
        			}
    				sum -= arr[leftIdx];
    				leftIdx += 1;
    			}
    			// S 이상이 얻어지는 가장 짧은 길이를 추가
    			lengths.add(rightIdx - leftIdx + 2);
    		}
    	}
    	
    	// 반복문에서 rightIdx == N-1인 경우를 확인하지 못하기 때문에 한 번 더 해준다.
    	if (sum >= S) {
			// sum이 S보다 작을 때까지 반복
			while (sum >= S) {
				// 값 하나가 S 이상이라면 길이 1이 무조건 최소 길이다.
    			if (leftIdx == rightIdx) {
    				lengths.add(1);
    				return;
    			}
				sum -= arr[leftIdx];
				leftIdx += 1;
			}
			// S 이상이 얻어지는 가장 짧은 길이를 추가
			lengths.add(rightIdx - leftIdx + 2);
		}
    }
    
    public static void main(String[] args) throws IOException {
        getInput();
        
        findMinLen();
        
        if (isPossible()) {
        	int minLen = Collections.min(lengths);
        	System.out.println(minLen);
        } else {
        	System.out.println(0);
        }
    }
}

---

회고

틀렸던 이유 1
처음에 투포인터를 양쪽 끝에서 시작하는 방식으로 적용해서 틀렸다.
이렇게 접근하면 큰 수가 가로막고 있는 경우에 문제를 제대로 해결할 수 없게 된다.

틀렸던 이유 2
반복문에서 마지막 인덱스를 확인하지 못하는 방식으로 작성해서 틀렸다.
마지막에 따로 확인하는 코드를 추가했다.