BOJ 17364 대회

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/17364

🧐 관찰 및 접근

#

• 어… 문제가 상당히 곤란해보인다. ㅋㅋㅋㅋ 첫번째 예제부터 친절해서 망정이지, 저런거 없었으면 당연히 1357번 1등한테 먹이고 3 출력했을 것 같다.
• $K = 1$일때부터 풀어보자.
  • 이때는 자명하게도 회의실 배정 문제와 같다.
  • 끝나는 시간을 기준으로 정렬하고, 그리디하게 가져가자.
• $K = 2$라면?
  • 형섭이는 1등이 먹고 남은 대회들에 대해서, 결국 위의 그리디한 방법으로 가져갈 것이다.
  • 이 때, 1등이 1, 3, 5, 7번 대회를 가져가서 남은 대회가 $(2, 3), (4, 5), (6, 7)$ 이라면 3개를 먹는 것이고,
  • 1, 4, 7번째 대회를 가져가서 남은 대회가 $(2, 3), (3, 4), (5, 6), (6, 7)$ 이라면 2개밖에 못먹는 것이다.
  • 이걸 DP같은걸로 어떻게 잘 가져가면 좋을것같은데..
• 엥? 근데 이거 약간 그리디하게 되지 않을까?
• 형섭씨도 그리디하게 먹으려고 하니, 형섭씨의 그리디를 의도적으로 방해하자.
  • 제일처음에 시간은 $T = 0$일때, 형섭씨는 첫번째 대회 $(1, 2)$를 출전하려고 한다.
    • 바아로 1등 출동
  • 힝잉잉거리면서 두번째 대회 $(2, 3)$을 출전하려고 한다.
    • 이걸 막을수는 없다. 그런데 이걸 나가고 나면 $(3, 4)$ 까지는 못나가시니 절대 안막아버리기
  • 그다음에 $(4, 5)$ 대회를 나가시려고하면, 이때 첫번째 대회 나가신분은 퇴근 후 집에서 요양중이시다. 바로 저기 보내버리자.
  • 다시 형섭씨는 힝잉잉거리면서.. 어쩌구
  • 우선순위 큐로 관리하면서 그리디하게 진행할 수 있을 것 같다!!!!!!!
  • ㅠ.ㅠ 바로 틀렸다. 이것만으로는 상대방이 너무 많은 대회를 나갈 수 있는 것 처럼 된다.
    • 아하, $(3, 5), (4, 5), (2, 7)$이 있다고 해보자. 단순하게 끝나는 시간만 관리해서는, 5일에 나와서 퇴근 후 저 $(2, 7)$ 대회에 나갈 수 있는것처럼 내가 해버렸다. 이러면 안되지
  • 음.. 어차피 세개 다 무조건 못먹는건 맞는데. 그리디라고 생각하면.. 쓸 수 있는 놈중 가장 마지막에 끝나는 놈을 쓰는게 유효한가? 다음 $(s, e)$에서 어차피 $e$는 꽤 크고, $s$가 빠른 놈이 들어오는게 문제인 것 같은데, 그러면 자유로운 친구가 더 오래 쉬도록 해야하는거 같다 .그러면 맞는거같다!! 셋같은걸로 지점을 잘 찾아보자.

💻 풀이

#

• 코드 (C++):

void solve(){
    int N, K; cin >> N >> K;
    vector<pii> contests(N);
    rep(i, 0, N) cin >> contests[i].first >> contests[i].second;
    sort(all(contests), [](const pii &a, const pii &b){
        if(a.second == b.second) return a.first < b.first;
        return a.second < b.second;
    });
    int ans = 0;
    int T = 0;
    multiset<int> st;
    rep(i, 0, K-1) st.insert(0);
    for(auto &[a, b]: contests){
        if(a <= T) continue;
        auto it = st.lower_bound(a);
        if(it == st.begin()){
            ans++;
            T = b;
            continue;
        }
        it--;
        st.erase(it);
        st.insert(b);
    }
    cout << ans;
}