[백준 7043] Cleaning Shifts

[ghdcksgml1]

Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn.

농부 존은 외양간 주변을 청소하기 위해서 그의 N마리의 소들을 배치했다.

He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.

그는 항상 한마리의 소로 청소하기를 원하고, 하루를 T 교대로 나누었다. 첫번째는 1이고 마지막은 T이다.

Each cow is only available at some interval of times during the day for work on cleaning.

각각의 소는 하루동안 청소하는데 오직 몇 차례 구간에 사용된다.

Any cow that is selected for cleaning duty will work for the entirety of her interval.

청소해야하는 곳이 정해진 어떤 소는 구간의 전체를 일해야한다.

Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning.

너의 직업은 농부 존을 도와 몇몇 소들을 근무에 배치하는 것이다. (i)모든 근무에 적어도 한마리의 소가 배치되어 하고, (ii)가능한 적은 소들이 청소에 참여하게 하기 위해서

If it is not possible to assign a cow to each shift, print -1.

만약 소들을 각각의 근무에 배치하는게 불가능하다면 -1을 출력하라.

---

;; 실버1인데 문제가 생각보다 어렵네요.. 많이 틀렸음 ㅜㅜ

문제는 약간 회의실 배정 문제와 비슷합니다.

1 ~ N까지의 구간을 모두 포함해야하는 소를 골라야하는데 최소로 골라야하고, 소의 구간은 겹쳐도 상관없습니다!

처음에 제출하면서 틀렸던 이유는 다음과 같은 반례를 생각하지 못해서였습니다.

입력 :

3 10

1 2

3 7

7 10

정답 : 3

위와같이 1 2, 2 3 처럼 연결되어있는게 아니라 1 2, 3 7 처럼 떨어져있어도  1 2 3 4 5 6 7 이 채워지기 때문에 정답을 구할 수 있었습니다.

여기까지는 쉬웠지만, 다음 반례를 처리하는데 오랜시간이 걸렸습니다.

입력 :

5 10

1 2

2 3

3 4

4 5

6 10

정답 : 4

정답이 4인 이유는 (1 2), (3 4), (4 5), (6 10) 이기 때문인데요. 여기서 (2 3)을 어떻게 처리해줄까?가 관건이였습니다.

이 구현이 어려웠던 이유는 위와같이 (2 3),(3 4)가 나오면 (2 3)을 포함을 안시키면 되는데

입력 :

3 10

1 2

2 3

4 10

정답 : 3

또 위와같이 연속으로 (x x+1)이 나오지 않으면 포함시켜야하는 경우도 있기때문에 이 조건을 처리하느라 미치는줄 알았습니다.

(다른 공부도 해야하는데 여기서 시간을 뺏기다니.. 고작 실버1 주제에.. ㅜㅜ)

그래서 저는 다음과 같이 구현했습니다. ( 아래 코드를 보면서 이해하는게 빠릅니다! )

현재 위치에서 1차로 통과한 구간을 한번 더 검사하는 방식

// 언어 : C++ , (성공/실패) : 1/6 , 메모리 : 2536 KB , 시간 : 8ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h> // memset

using namespace std;

int N,T;
vector<pair<int,int>> v;

bool compare(pair<int,int> a,pair<int,int> b){
    if(a.first == b.first){
        return a.second > b.second;
    }
    return a.first < b.first;
}

int main(void){
    // 입출력 속도 최적화
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>T;
    for(int i=0;i<N;i++){
        int a,b; cin>>a>>b;
        v.push_back({a,b});
    }
    sort(v.begin(),v.end(),compare);

    v.push_back({1000000000,0});
    bool trigger=0;
    int x=0;
    int y=0;
    int cnt=0;
    for(int i=0;i<v.size();i++){
        if(v[i].first<=x+1){
            if(y<v[i].second){
                y = v[i].second;
                trigger=true;
            }
            if(v[i+1].first > x+1 && trigger){ // 다음 숫자올 숫자의 first가 전에 비교한 값의 second+1보다 크다면
                // ex.) 1 4    3 5    5 7 인 경우에는 현재 3 5이므로 카운팅하지 않는다.
                cnt++;
                x=y;
                trigger=false;
            }
        }
    }

    if(y==T) cout<<cnt<<'\n';
    else cout<<"-1"<<'\n';

    return 0;
}

---

chores: 허드렛일

barn: 외양간

shift: 교대근무

interval: 구간

entirety: 전체, 전부

involve: 관련시키다, 참여시키다