백준 27968번 - 사사의 사차원 사탕 봉지

# 문제

27968번 - 사사의 사차원 사탕 봉지

https://www.acmicpc.net/problem/27968

 

누적합 + 이진탐색 문제이다.

입력의 개수가 많기 때문에 순차탐색으로는 해결할수 없다..

 

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

public class Main {
    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());   // 최대 횟수
        
        // 사사가 꺼낸 사탕의 누적합 배열
        long[] candySum = new long[m + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= m; i++) {
            candySum[i] = candySum[i - 1] + Long.parseLong(st.nextToken());
        }
        
        // 아이들이 원하는 사탕 개수 배열
        long[] kids = new long[n];
        for (int i = 0; i < n; i++) {
            kids[i] = Long.parseLong(br.readLine());
        }
        
        // 결과 저장
        StringBuilder sb = new StringBuilder();
        for (long k : kids) {
            int idx = Arrays.binarySearch(candySum, k);
            if (idx < 0) idx = -(idx + 1); // 삽입 위치 계산
            if (idx > m) sb.append("Go away!").append("\n");
            else sb.append(idx).append("\n");
        }
        
        // 결과 출력
        System.out.print(sb);
    }
}