[백준 / BOJ] C++ 27968 사사의 사차원 사탕 봉지

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

 

문제

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

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

 

 

풀이

누적 합 + 이분 탐색 문제로 사탕을 꺼낼 때마다 사탕의 수는 누적되므로 몇 번 꺼냈을 때 사탕이 얼마나 있는지 알 수 있다. 그리고 아이가 받고 싶어하는 사탕의 수가 정확히 꺼낸 수와 동일하지 않을 수 있으므로 lower_bound 함수로 최초로 같거나 큰 수의 사탕이 있는 인덱스를 찾는다. 만약 범위를 초과하면 Go away!를 출력하고 그렇지 않으면 인덱스를 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<long long> a(m + 1);
  for (int i = 1; i <= m; i++) {
    cin >> a[i];
    a[i] += a[i - 1];
  }
  for (int i = 0; i < n; i++) {
    long long b;
    cin >> b;
    int idx = lower_bound(a.begin(), a.end(), b) - a.begin();
    if (idx > m)
      cout << "Go away!\n";
    else
      cout << idx << '\n';
  }
  return 0;
}