[SCCC] 회의실 배정_1931번

손시연·2022년 6월 12일
0

SCCC

목록 보기
14/18

회의실 배정_1931번

코드

#include <bits/stdc++.h>
using namespace std;

int Solve(vector<pair<int, int>> meeting) {
    int answer = 0;
    //종료시간을 기준으로 정렬
    sort(meeting.begin(), meeting.end());

    int time = 0;
    for (int i = 0; i < meeting.size(); i++) {
        if (meeting[i].second >= time) {
            time = meeting[i].first;
            answer++;
        }
    }
    
    return answer;
}


int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> meeting(n);
    for (int i = 0; i < n; i++) 
        cin >> meeting[i].second >> meeting[i].first;  
        //<종료시간, 시작시간>

    cout << Solve(meeting);

    return 0;
}

풀이노트

핵심개념 : 그리디

  • 회의 종료 시간이 가장 짧은 회의 선택
    • sort(meeting.begin(), meeting.end()) (종료시간을 기준으로 정렬)
  • 겹치는 시간대 삭제
    • if (meeting[i].second >= time)
  • 다시 종료 시간이 가장 빠른 회의를 선택하는 방식
    • time = meeting[i].first

C++ 개념

  • vector<bool> check(n, true)
    • n의 길이만큼 true 로 초기화
  • start.erase(start.begin()+i)
    • start[i] 원소 삭제
  • vector<pair<int, int>> 접근 :vec[i].first, vec[i].second 로 접근

소요시간 : 2일

profile
Server Engineer

0개의 댓글