[백준] Q1806 부분합 JAVA

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

1806번: 부분합

1. 문제의 유형 및 이해

투포인터

10,000이하 자연수로 이루어진 길이 N자리 수열이 주어진다.

이 수열에서 연속된 수들의 부분합 중에서 그 합이 S이상이 되는 것 중 가장짧은 길이를 구하는 프로그램

$10 <= N <= 100,000$ 과 $0<S<=100,000,000$ 이 주어진다.

 

문제에서 뽑아내는 키워드는 '자연수', '연속된 부분합' 과 제한조건을 볼 수 있었습니다.

연속된 부분합이라는 것에서 차례차례 더해가며 O(N) 시간복잡도로 합이 S이상인지 확인할 수 있습니다. 

또한, '자연수'라는 조건 때문에 순서대로 빼었을 때 기존보다 값이 낮아진다는 것을 알 수 있습니다.

만약, '자연수'가 아니라 음수도 섞여있는 조건과 '가장 긴'이라는 조건이였다면, 함부로 빼서는 안 될 것입니다.

 

2. 문제 접근 방법

어떠한 구간 [left, right]의 합을 추적합니다.

[left ~right]값이 S보다 작다면 right를 증가시켜보고, 크다면 left값을 빼주도록 합니다.

right는 그다음 값을 보고 있기 때문에 [a,b)인 개구간이라서 둘 사이의 거리는 b-a로 구할 수 있습니다.

 

투포인터나 이분탐색과 같이 어떠한 범위에 민감한 알고리즘은 구현하면서 디테일적인 요소들에 대해 잘 생각하면서 구현해야합니다. 초기에 어떠한 상태에서 시작할 것이며 경계 부분을 어떻게 설정하고 하는 것들에 대해서는 많은 경험과 구현 전에 디테일하게 생각하고 들어가는 것이 좋은 것 같습니다.

package solvedac.level5.gold4;

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

/**
 * @문제번호 : Q1806
 * @문제이름 : 부분합
 * @난이도 : Gold IV
 * @date : 2022.01.11
 * @author : pcrmcw0486
 * @문제이해
 * 10,000 이하 자연수로 이루어진 길이 N짜리 수열이 있다.(자연수)
 * 연속된 수들의 부분합 중 그 합이 S이상이 되는 것 중 가장 짧은 것의 길이를 구하는 프로그램.
 * 10<=N<=100,000 O(N)이면 충분히 가능하다.
 * 0<S<=100,000,000  >> int 형으로 가능하다.
 * @알고리즘
 * twoPointer
 * @접근방법
 * '연속된 부분합' + '가장짧은' 에 초점을 맞춘다.
 * left 이전 시작 지점 right현재 내가 보는 지점.
 * [left ~right]까지의 합을 O(N)으로 구할 수 있고, 만약 S보다 커진다면 사이 길이를 계산하고,
 * S보다 작아지도록 낮춰준다.
 * 이러한 방식이 가능한 이유는 자연수 이기 때문이다.
 * 만약 음수가 섞여있다면, 보장하지 못한다. 양수이기때문에 S는 항상 양수이고 빼주었을 때 낮아지기 때문이다.
*/
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());
        st = new StringTokenizer(br.readLine());
        int ans =Integer.MAX_VALUE;
        int[] data = new int[N];
        for (int i = 0; i < N; i++) data[i] = Integer.parseInt(st.nextToken());
        int left =0, right=0, sum=0;
        while(true){
            if(sum<S){
                if(right == N) break;
                sum += data[right++];
            }else{
                ans = Math.min(ans, right - left);
                sum -= data[left++];
            }
        }
        System.out.println(ans==Integer.MAX_VALUE?0:ans);
    }
}