Code Forces 279B

투 포인터 알고리즘 사용

high와 low를 같은 방향으로 증가시킨다.

양수로만 이루어진 배열이기 때문에 구간이 늘어날수록 sum의 값은 커질 수 밖에 없다.

high만 늘리다가, sum의 값이 T를 넘는 경우에는 low값을 sum이 T의 범위에 들어올때 까지 증가시킨다.

이 과정을 high가 N의 범위까지 돌면서 답을 찾는다.

import java.io.*;
import java.util.StringTokenizer;
 
public class Main {
 
    // input
    private static BufferedReader br;
 
    // variables
    private static int N, T;
    private static int[] arr;
 
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        input();
 
        bw.write(solve());
        bw.close();
    } // End of main()
 
    private static String solve() {
        StringBuilder sb = new StringBuilder();
 
        int ans = 0;
        int low = 0;
        int sum = 0;
 
        for (int high = 0; high < N; high++) {
            sum += arr[high];
 
            while (sum > T) {
                // high만 증가시키면서, 증가한 sum값을 low를 증가시키면서 sum 값을 감소시킨다.
                // sum은 한쪽 방향으로만 증가한다.
                sum -= arr[low];
                low++;
            }
 
            ans = Math.max(ans, high - low + 1);
        }
 
        sb.append(ans);
        return sb.toString();
    } // End of solve()
 
    private static void input() throws IOException {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        T = 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());
        }
    } // End of input()
} // End of Main class