[백준/C++] 알고리즘 19700번 - 수업

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 19700번 - 수업을 풀어보도록 하겠습니다.

 

 

https://www.acmicpc.net/problem/19700

19700번: 수업

 

[문제 접근]

자신보다 키 큰 사람이 ki명 이상이면 나간다는 조건 때문에 정렬이 필요하다는 생각이 들었습니다.

이 때 오름차순으로 할지 혹은 내림차순으로 할지 판단하기 위해  각각 오름차순, 내림차순 정렬하여 한 명씩 새로운 팀을 만들어 배치하는

작업을 해보았습니다. 오름차순으로 할 경우, 특정 한 명을 배정할 때 그 팀 안의 모든 사람들이 ki조건을 따져야 했고, 내림차순으로 할 경우 배정을 하려는 사람의 ki조건만 따지면 되었습니다. 그래서 내림차순으로 정렬을 했습니다.

한편, 여기에 그리디의 개념이 들어가는데 최소의 팀을 만들기 위해서는 사람을 배정할 때 인원이 가장 많은 팀에 들어가야 합니다.

인원이 가장 많은 팀에 들어가야하는 이유는, ki명이하를 만족하는 팀들 중에 가장 많은 팀에 들어가야 우리가 원하는 최소로 팀을 만들 수 있기 때문입니다.

N이 50만이하라는 것을 고려하여 set 자료구조를 생성하여 새로운 팀을 하나씩 만들고, 팀원을 조건에 맞추어 배치하였습니다.

set자료구조에는 팀의 인원을 원소로 받았습니다.

그리고 수강생을 배정할 때 자신보다 키 큰 사람이 ki명 미만(ki-1이하)인 팀을 찾아야하기 때문에, set자료구조에서 팀의 인원을 계산할 때 음수로 넣어서 사용해야합니다.

 

[풀이 전략]

1. 인원을 저장한 배열을 키의 내림차순으로 정렬합니다.

2. multiset 자료구조를 생성합니다.

3. 수강생 한 명씩  접근합니다.

4. multiset에 수강생의 ki-1이하가 존재하는 지 찾기 위해 + 가장 많은 팀에 들어가기 위해, lower_bound(-arr[i].second + 1)을 이용합니다.

5.만약 발견할 수 없으면 새로운 팀을 만듭니다 -> multiset에 -1을 추가합니다.

6.존재하면 그 값을 지우고 (그 값-1)을 multiset에 추가합니다. 

7. multiset의 사이즈를 출력합니다.

 

[코드]

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;


int n ; 
pair<int,int> arr[500001];

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n ;

    for(int i = 0; i < n ; i++){
        int h, k ;
        cin >> h >> k ; 
        arr[i].first = h ;
        arr[i].second = k ;
    }
    
    sort(arr, arr+n, greater<pair<int,int>>());

    
    multiset<int> s;
    
    for(int i = 0 ; i < n ; i++){
      auto lower = s.lower_bound(-arr[i].second + 1) ;
      if( lower == s.end()){
         s.insert(-1);
      } else {
          // s[lower- s.begin()]--; <- 이렇게 접근 못하기 때문에 아래처럼 작성.
          int v = *lower;
          s.erase(lower);
          s.insert(v -1);
      }
    }

    cout << s.size(); 
}

 

[배울 점]

- set은 특성상 오름차순으로 자동 정렬됨.

- set에서도 lower_bound 사용 가능. 

- set erase의 매개인자는 값뿐만 아니라 iterator도 가능.