boj 3985 롤 케이크

www.acmicpc.net/problem/3985

3985번: 롤 케이크

가장 많은 조각을 받을 것으로 기대하고 있던 방청객의 번호는 입력으로 주어지는 l과 r의 차이가 큰 값을 출력하면 됩니다.

하지만 앞의 방청객이 원하는 조각을 받으면 뒤의 방청객은 받지 못하는 상황이 있을 수 있습니다.

 

입력으로 1번 방청객부터 N번 방청객까지 원하는 조각의 범위가 주어지면 list에 바로 방청객의 번호를 저장해줍니다.

이때 번호가 이미 저장되어있으면 저장하지 않고, 번호를 저장한 횟수를 num에 저장하여 num[i]이 가장 큰 방청객의 번호를 출력해주시면 됩니다.

 

 

#include <iostream>
using namespace std;
 
int list[1001], num[1001];
int L, N;
 
void func() {
    int maxlength = 0;
    int maxidx = 0;
    for (int i = 1; i <= N; i++) {
        if (maxlength < num[i]) {
            maxlength = num[i];
            maxidx = i;
        }
    }
 
    cout << maxidx << '\n';
}
 
void input() {
    int maxlength = 0;
    int maxidx = 0;
    int l, r;
    cin >> L >> N;
    for (int i = 1; i <= N; i++) {
        cin >> l >> r;
        if (maxlength < r - l) {
            maxlength = r - l;
            maxidx = i;
        }
 
        for (int j = l; j <= r; j++) {
            if (list[j]) continue;
            list[j] = i;
            num[i]++;
        }
    }
 
    cout << maxidx << '\n';
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}