백준 1806 부분합

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

문제 제목 그대로 부분합을 구할 수 있는지를 물어보는 문제이다.
투포인터를 통해 O(N)의 시간복잡도로 통과할 수 있다.

시작점에 두개의 포인터를 설정하고 구간합이 작으면 오른쪽 포인터를 밀고,
구간합이 크다면 작은 범위가 있는지를 파악하기 위해 왼쪽 포인터를 밀면 된다.
종료 조건은 부분합이 작아 오른쪽 포인터를 밀었는데 더이상 원소가 없는 경우가 종료 조건이다.

1) 파이썬 코드

n,target = list(map(int,input().split()))
arr = list(map(int,input().split()))
ans = 100001
prefix_sum,s,e = 0,0,0
while True:
    if prefix_sum >= target:
        prefix_sum -= arr[s]
        ans = min(ans, e-s)
        s += 1
    elif e == n:
        break
    else:
        prefix_sum += arr[e]
        e += 1

if ans == 100001:
    print(0)
else:
    print(ans)

2)자바 코드

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

public class Main {
    private static final int INF = 1000000000;
    private static int n,target;
    private static int[] arr;
    private static int ans = 1000001;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int target = Integer.parseInt(st.nextToken());

        arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int s = 0; int e = 0; int prefix_sum = 0;
        while (true) {
            if (prefix_sum >= target) {
                prefix_sum -= arr[s];
                ans = Math.min(ans,e-s);
                s += 1;
            } else if (e == n) {
                break;
            }else{
                prefix_sum += arr[e];
                e += 1;
            }
        }
        if (ans == 1000001) {
            System.out.println(0);
        } else{
            System.out.println(ans);
        }

    }

}