아이디어

• A[1]~A[i]의 합을 Aacc[i]라고 할 때, Aacc를 이진탐색하여 처음 B[i] >= Aacc[idx]가 되는 idx를 찾으면 된다.
• Java의 Arrays.binarySearch()를 사용한다면, 탐색 실패 시 리턴되는 음수 값의 의미를 이용하면 빠르다. (https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#binarySearch-int:A-int-)
• Aacc[]와 B[]는 32-bit 범위를 벗어남에 주의

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int N, M, curIdx;
	static long cur;
	static int[] A;
	static long[] Aacc;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		
		A = new int[M+1];
		Aacc = new long[M+1];
		tk = new StringTokenizer(rd.readLine());
		for (int i=1; i<=M; i++) {
			A[i] = Integer.parseInt(tk.nextToken());
			Aacc[i] = Aacc[i-1] + A[i];
		}
		for (int i=1; i<=N; i++) {
			long B = Long.parseLong(rd.readLine());
			int idx = Arrays.binarySearch(Aacc, B);
			int ans;
			if (idx > 0) {
				ans = idx;
			}
			else {
				ans = -(idx + 1);
			}
			
			if (ans > M)
				sb.append("Go away!\n");
			else
				sb.append(ans).append('\n');
		}

		System.out.println(sb);
	}
}

메모리 및 시간

• 메모리: 74096 KB
• 시간: 752 ms

리뷰

• 처음에 문제 이해를 잘못하는 바람에 골때렸던 문제