[백준] 부분합 (골드4)

https://www.acmicpc.net/problem/1806
LIS 활용 문제 + arraylist 뒤에서 부터 값 가져오기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int n, s;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

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

        // LIS -> 비교해서 가장 짧은 거 출력
        ArrayList<Integer> d = new ArrayList<>();
        for(int x : arr){
            int i = Collections.binarySearch(d, x);
            if(i<0) i=-i-1;
            if(i==d.size()) d.add(x);
            else d.set(i,x);
        }

        int sum = 0;
        int ans = 0;
        for(int i=d.size()-1;i>=0;i--){
            if(sum >= s) {
                System.out.println(ans);
                return;
            }
            else{
                sum += d.get(i);
                ans += 1;
            }
        }
        System.out.println(0);

    }
}

=> 문제 이해를 잘못함 => 투포인터로 수정

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int n, s;
    static int[] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

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

        // 투 포인터로 진행해서 우측 포인터가 끝까지 가면 끝
        int l=0;
        int r=0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;

        // 좌, 우로 계속 늘려가기
        //while(r!= arr.length){ 로 쓰면 틀림
        while(true){
            if(sum>=s){
                ans = Math.min(ans, r-l);
                sum -= arr[l];
                l++;
            }

            else if(r==arr.length) break;
            else{
                sum += arr[r];
                r++;
            }
        }

        if(ans != Integer.MAX_VALUE)
            System.out.println(ans);
        else
            System.out.println(0);

    }
}