https://www.acmicpc.net/problem/1931
문제
코드
#include <bits/stdc++.h>
using namespace std;
pair<int, int> s[100005];
bool cmp(pair<int, int> &a, pair<int, int> &b)
{
if (a.second == b.second)
{
return a.first < b.first;
}
return a.second < b.second;
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i=0; i<n; i++)
{
cin >> s[i].first >> s[i].second;
}
sort(s, s+n, cmp);
int ans=0;
int t=0; //현재시간으로 0으로 초기화
for (int i=0; i<n; i++)
{
if (t > s[i].first) //각 회의가 겹치면 안 됨
continue;
ans++;
t = s[i].second;
}
cout << ans;
}
풀이
그리디로 해결했다.
pair에서 first = 시작시간 / second = 종료시간이다.
원하는 기준으로 정렬하기 위해 sort에 cmp함수를 인자로 준다.
cmp함수는 종료시간이 빠른게 앞에 오도록 하고, 만약 종료시간이 서로 같다면 시작시간이 빠른게 앞에 오도록 한다.
종료시간이 같을 때 시작시간이 빠른게 앞에 와야하는 이유는 정렬된 것들을 앞에서 부터 확인하여 조건을 따져가며 ans를 증가시킬건데 예를들어 (6,8), (10,10), (8,10) 과 (6,8), (8,10), (10,10)의 경우를 비교해보면 전자는 ans가 2증가하는데에 반해 후자는 ans가 3증가한다. 결과적으로 시작시간과 종료시간이 같은 경우 때문에 종료시간이 같을 때, 시작시간이 빠른게 앞에 와야하는 것이다.
결과
'Koala - 5기 > 기초 알고리즘 스터디' 카테고리의 다른 글
[BOJ/PYTHON] - 15969 행복 (0) | 2022.03.06 |
---|---|
[백준/python] 14650:걷다보니 신천역 삼(small) (0) | 2022.03.03 |
[백준/C++] 4963번 섬의 개수 (0) | 2022.02.28 |
[백준/python] 17608 막대기 (0) | 2022.02.28 |
[백준/c++] 3029번 경고 (0) | 2022.02.28 |