[BOJ] 백준 3985 롤 케이크

출처: https://www.acmicpc.net/problem/3985

 Input 

10

3

2 4

7 8

6 9

 

 Output 

3

1

 

1..N 방청객 순서대로 기대하는 케이크 개수와 받을 수 있는 케이크를 처리하므로

순차적으로 기존 값과 비교하며 구할 수 있습니다.

① 기대하는 케이크 개수

    ▶ [a b]  → a~b번까지 케이크 개수 = b - a + 1

② 실제 받을 수 있는 케이크 개수

    ▶ 앞선 방청객들이 받은 케이크를 제외해서 셉니다.

---

#include <iostream>
using namespace std;
 
bool canTake[1001];
int L, N;
int firstCnt = 0, firstAns, secondCnt = 0, secondAns;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    cin >> L >> N;
    int left, right, temp;
    for(int idx=1; idx<=N; idx++){
        cin >> left >> right;
        
        // 기대하고 있는 케이크 개수
        if(firstCnt < right - left + 1){
            firstCnt = right - left + 1;
            firstAns = idx;
        }
 
        temp = 0; // 실제 받는 케이크 개수
        for(int i=left; i<=right; i++){
            if(!canTake[i]){
                temp++;
                canTake[i] = true;
            }
        }
        // 기존에 받은 사람보다 더 많이 받는 경우
        if(secondCnt < temp){
            secondCnt = temp;
            secondAns = idx;
        }
    }
 
    cout << firstAns << '\n' << secondAns;
}