BOJ 6010 - Music Notes 문제풀이

문제를 읽고 이해하기

FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for B_i (1 <= B_i <= 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B_1, note 2 from time B_1 through just before time B_1 + B_2, etc.

However, recently the cows have lost interest in the song, as they feel that it is too long and boring. Thus, to make sure his cows are paying attention, he asks them Q (1 <= Q <= 50,000) questions of the form, "In the interval from time T through just before time T+1, which note should you be playing?" The cows need your help to answer these questions which are supplied as T_i (0 <= T_i <= end_of_song).

Consider this song with three notes of durations 2, 1, and 3 beats:

Here is a set of five queries along with the resulting answer:

입력

• Line 1: Two space-separated integers: N and Q
• Lines 2..N+1: Line i+1 contains the single integer: B_i
• Lines N+2..N+Q+1: Line N+i+1 contains a single integer: T_i

출력

• Lines 1..Q: For each query, print a single integer that is the index of the note that the cows should be playing.

재정의와 추상화

(영문 해석은 따로 하지 않겠습니다.)

T_i 부분을 해결하는 과정에 C++ STL의 lower_bound를 사용하는 것이 문제의 핵심이다.

이 함수를 떠올리지 못한다면 아래와 같은 실수를 했을 것이다. (나포함ㅎ)

1. B_i를 저장하는 대에 과도하게 많은 메모리 사용(최대 20억 bytes)으로 인해 메모리 초과
2. 'notes'라는 이름의 vector에 범위를 make_pair(시작, 끝 - 1)로 저장한 후 T_i 처리부에서 notes의 0번째 인덱스부터 끝까지 모두 탐색하므로 인한 시간 초과 (O(QN))

이런 실수를 남발하다가, 어떻게 하면 메모리도 적게 사용하면서 시간도 오래 안걸릴 수 있을까 생각하다가, 이진 탐색(binary_search)를 떠올렸고, 이진 탐색에 관련한 레퍼런스를 찾다가, 뿌리가 되는 lower_bound를 접하게 되었다.

> lower_bound에 대해 배우러 가기

lower_bound는 찾으려는 값이 없을 경우, 찾으려는 값 이상의 값들 중 최솟값을 찾는 함수이다.

이를 이용하기 위해서 노트를 저장할 때, 해당 노트의 범위가 a 이상 b 미만(a <= Value < b)이라면, 최댓값(b - 1)만 저장해놓는다. 그리고 T_i 부분에서 lower_bound()를 이용한다.

lower_bound는 찾으려는 값 이상의 값들 중 최솟값이 위치하는 곳의 이터레이터(지시자)를 반환하므로, (해당 위치의 이터레이터) - (벡터의 처음 위치의 이터레이터) + 1이 정답이다.

index	0	1	2
value	1 (2 - 1)	2 (3 - 1)	5 (6 - 1)
note number	1	2	3

코드 작성

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int now = 0;
    vector<int> notes;
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        int count;
        cin >> count;
        notes.push_back(now + count - 1);
        now += count;
    }

    for (int i = 1; i <= q; i++) {
        int question;
        cin >> question;
        auto it = lower_bound(notes.begin(), notes.end(), question);
        cout << it - notes.begin() + 1 << '\n';
    }

    return 0;
}