[이분 탐색] 16510번 - Predictable Queue

🔗 문제 링크

백준 16510번 - Predictable Queue

📝 풀이

일반 배열을 두고 배열의 크기만큼 계속 돌면서 누적합을 구하면 시간초과가 뜬다.
혁진이가 일할 수 있는 시간을 의미하는 정수 T를 받을때
배열에 부분합으로 받아서 이진탐색을 하면 해결된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class PredictableQ_16510 {
	
	public static void main(String [] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int[] tasks = new int[N+1];
		
		for(int i = 0; i < N; i++) {
			tasks[i+1] = tasks[i] + Integer.parseInt(st.nextToken());
		}
		
		for(int i = 0; i < M; i++) {
			int time = Integer.parseInt(br.readLine());
			
			int left = 1;
			int right = N;
			
			while(left <= right) {
				int mid = (left + right) / 2;
				
				if(tasks[mid] > time) right = mid - 1;
				else left = mid + 1;
				
			}

			System.out.println(right);
		}
		
		
	}
}