[백준 1392] 노래 악보 (C#, C++) - soo:bak

문제 링크

1392번 - 노래 악보

설명

각 악보가 소요하는 초 단위 길이가 주어질 때, 특정 시각에 부르고 있는 악보 번호를 묻습니다. 0초부터 시작하며 각 악보는 연속해 이어집니다.

접근법

각 악보의 길이를 앞에서부터 누적하여 배열에 저장합니다. 이 배열의 i번째 값은 i번 악보가 끝나는 시각입니다.

질의로 주어진 시각 t에 대해, 누적 배열에서 t보다 큰 값이 처음 나오는 위치를 찾으면 그 위치가 해당 시각에 부르고 있는 악보 번호입니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var first = Console.ReadLine()!.Split();
    var n = int.Parse(first[0]);
    var q = int.Parse(first[1]);

    var pref = new int[n];
    for (var i = 0; i < n; i++) {
      var len = int.Parse(Console.ReadLine()!);
      pref[i] = len + (i == 0 ? 0 : pref[i - 1]);
    }

    for (var i = 0; i < q; i++) {
      var t = int.Parse(Console.ReadLine()!);
      var idx = 0;
      while (idx < n && pref[idx] <= t)
        idx++;
      Console.WriteLine(idx + 1);
    }
  }
}

C++

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

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, q; cin >> n >> q;
  vi pref(n, 0);
  for (int i = 0; i < n; i++) {
    int len; cin >> len;
    pref[i] = len + (i ? pref[i - 1] : 0);
  }

  while (q--) {
    int t; cin >> t;
    int idx = upper_bound(pref.begin(), pref.end(), t) - pref.begin();
    cout << (idx + 1) << "\n";
  }

  return 0;
}