백준 1931 : 회의실 배정

문제

백준 1931 : 회의실 배정

코드

#include <iostream>
#include <algorithm>
using namespace std;
pair<int,int> meeting[100000];
bool compare(pair<int,int>& a,pair<int,int>& b){
    if(a.second!=b.second)
        return a.second<b.second;
    else{
        return a.first<b.first;
    }
}
int main(){
   int N;
   cin>>N;
   
    for(int i=0;i<N;i++){
        cin>>meeting[i].first>>meeting[i].second;
    }
    
    sort(meeting,meeting+N,compare);
    
    int t=0;//회의가 끝난 시각
    int cnt=0;
    for(int i=0;i<N;i++){
        if(meeting[i].first<t)
            continue;
        t=meeting[i].second;
        cnt++;
    }
    cout<<cnt;
}

트러블 슈팅

1. 정렬 기준을 정확하게 잡을 것

회의 시작 시간을 first , 회의 끝난 시간을 second라 하자.
second 기준으로 오름차순 정렬하되 , second값이 같다면 first가 작은 것부터 큰 순서대로 오름차순으로 정렬해야한다.
왜냐하면 (2,2) (1,2) 의 경우
(2,2) (1,2)로 정렬되어 있다면 (1,2)를 경우에 포함시키지 못하고 지나칠 것이기 때문이다.

2. 시간초과 이슈

#include <iostream>
#include <algorithm>
using namespace std;
pair<int,int> meeting[100000];

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

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

    for(int i=0;i<N;i++){
        int start,end;
        cin>>meeting[i].first>>meeting[i].second;
    }
 
    //sort()이용
    sort(meeting, meeting+N, compare);
    
    int cnt=0;
    pair<int,int> before={0,0};
    int before_idx;
    int flag=0;
    while(true){
        //before회의의 끝난시각보다 시작시각이 더 큰 회의를 선택
        if(cnt==0){
            before.first=meeting[0].first;
            before.second=meeting[0].second;
            before_idx=0;
            cnt++;
        }
        else{
            if(before_idx==N-1)
                break;
            for(int i=before_idx+1;i<N;i++){
                if(meeting[i].first<before.second)
                    continue;
                flag=1;
                before.first=meeting[i].first;
                before.second=meeting[i].second;
                before_idx=i;
                cnt++;
                break;
            }
            if(flag==0)
                break;
                
        }
    }
    
    
    cout<<cnt;
}

while문안에 for문으로 시간복잡도가 O(N^2)으로 구현했었는데,
그럴 필요가 없는 문제였다.
-> 백준에서 시간초과 발생
O(N)으로 문제가 풀린다.

백준 2217 : 로프

문제

백준 2217 : 로프

코드

#include <iostream>
#include <algorithm>
using namespace std;
int weight[100000];
bool compare(int& a,int& b){
    return a>b;
}
int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>weight[i];
    
    sort(weight,weight+N,compare);
    
    int result=0;
    int cnt=1;
    for(int i=0;i<N;i++){
        
        if(result>weight[i]*cnt){
            cnt++;
            continue;
        }

        result=weight[i]*cnt;
        cnt++;
    }
    
    cout<<result;
    
}

트러블 슈팅

#include <iostream>
#include <algorithm>
using namespace std;
int weight[100000];
bool compare(int& a,int& b){
    return a>b;
}
int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>weight[i];
    
    sort(weight,weight+N,compare);
    
    int result=0;
    int cnt=0;
    for(int i=0;i<N;i++){
        cnt++;
        if(result>weight[i]*cnt)
            break;
        result=weight[i]*cnt;
    }
    
    cout<<result;
    
}

중간에 if문 걸렸다고 break를 하면안됨
반례

4
200
99
98

break를 continue로 바꾸고 cnt++를 문제의 조건에 맞게 잘 해줄 것.

백준 2217 : 로프

문제

백준 2217 : 로프

코드

#include <iostream>
#include <algorithm>
using namespace std;
bool compare(int& a,int& b){
    return a>b;
}
int A[50];
int B[50];
int main(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
        cin>>A[i];
    for(int i=0;i<N;i++)
        cin>>B[i];
        
    sort(A,A+N);
    sort(B,B+N,compare);
    
    int cnt=0;
    for(int i=0;i<N;i++)
        cnt+=A[i]*B[i];
    cout<<cnt;
    
}