[백준] 1806번 부분합

문제 출처 

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

1806번: 부분합

 

 

 

접근 방식 및 풀이

- 투포인트 알고리즘 이용

[Algorithm] - [알고리즘] 투포인트 알고리즘

 

- 배열의 순서는 움직일수 없으므로, left/right 포인터 2개를 이용하여 풀이. 

 

 

 

소스 코드 

 
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    private static int[] arr;
    private static int n;
    private static long s;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.nextLong();
        arr = new int[n];
        for (int i = 0; i <n ; i++) {
            arr[i] = sc.nextInt();
        }
 
        int ans = 100001, sum = 0;
        int left = 0, right =0;
        //  left, right 포인터로 합이 s이상 일때 right-left가 제일 작은것을 찾는다.
        while(true){
            if(sum >= s){// s를 찾아야하는데 지금까지 연속해서 더한 부분합이 더 크다면 leftpointer를 옮겨주고, 옮겼으므로 sum에서 빼준다.
                sum -= arr[left];
                ans = Math.min(ans, (right- left));
                left++;
            } else if(right == n) {
                break;
            }else{
                sum += arr[right];
                right++;
            }
        }
 
        if(ans == 100001){ // 처음에 초기화한 조건 그대로라는 이야기는 조건에 만족하는게 없다는 뜻, 그러므로 0출력
            System.out.println(0);
        }else {
            System.out.println(ans);
        }
    }
}
 

 

 

결과