[백준 16510] Predictable Queue

 

일반적인 배열이나 부분합 배열로 풀면 시간초과가 난다.

 

나는 부분합 배열을 이분탐색하는 방식으로 풀었다.

이것말고도 풀이가 많을것 같은데 푼 사람이 얼마없어서 다른 방법은 못 찾았다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n+1];
        for(int i=0; i<n; i++)
            a[i+1] = a[i] + sc.nextInt();
        
        while(m-->0) {
            int t = sc.nextInt();
            
            int left = 1;
            int right = n;
            while(left <= right) {
                int mid = (left + right)/2;
                if(a[mid] > t) right = mid-1;
                else left = mid+1;
            }
            System.out.println(right);
        }
    }
}