[백준/c++] 177262 - 팬덤이 넘쳐흘러

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

17262번: 팬덤이 넘쳐흘러

---

1) 풀이

예전엔 온종일 풀어도 풀리지 않던 문제가 오늘 딱! 의외로 쉽게 풀려버렸다.

이럴 땐 기분이 짜릿하기도 하지만 한편으로는 허무한... 그래두 내가 실력이 늘었다는 증거겠지?

 

이 문제는 '그리디 알고리즘'에 관한 문제이다. 

(그리디 알고리즘에 대한 자세한 사항은 아래 참고자료 링크를 보길 바란다. 

시간이 된다면, 블로그에 적어보겠다!)

이 문제를 처음 접했을 때는 어떻게 접근해야 할지 감이 안 와서 int 배열을 만든 다음,

해당 시간에 온 학생수를 (s와 e를 각 시작 인덱스와 끝 인덱스로 정한 뒤) 카운팅하는 방법을 생각했었는데,

그러다보니 그 시간에 머물렀던 학생 수만 알 수 있을 뿐, 어떤 학생이 언제 와서 언제 가는지 확인할 방법이 없었다!

하지만 오늘 그리디 알고리즘에 대해 찾아보던 중, 참고자료에 있는 블로그를 참고하고 아이디어💡를 얻어 풀 수 있었다!

 

아이디어를 생각하고 나면 쉬운 문제인데 결론부터 말해보자면,

팬들 중 가장 늦게 학교에 도착하는 팬의 시간, 그리고 팬들 중 가장 빨리 학교를 떠나는 팬의 시간을 구하면 된다.

(가장 늦게 도착하는 시간을 smax, 가장 빨리 학교를 떠나는 시간을 emin이라고 부르겠다.)

 

1) 각 팬들이 학교에 머무는 시간이 전부 혹은 부분적으로 겹치지 않는 경우

문제 설명 그림

위 예시에서 smax는 5, emin은 4이다.

팬들이 오는 시간이 일부만 겹칠 경우, smax가 emin보다 클 수밖에 없고 답은 smax-emin으로 출력해야 한다.

다른 경우는, 이와 반대로 생각하면 되는데 즉 smax가 emin보다 작거나 같은 경우이다.

 

2) 각 팬들이 학교에 머무는 시간이 모두 겹칠 경우

문제 설명 그림

위의 A, B, C 팬들은 학교에 있는 시간이 모두 겹친다.

이때 smax는 2, emin은 4가 되고 위의 상황과는 다르게 smax가 더 작다.

가장 학교에 늦게 도착하는 팬(smax)이 가장 빨리 학교를 떠나는 팬(emin)의 시간보다 빠르다는 것은

최소 smax에는 모든 팬들이 도착해있는 경우이므로 머무는 시간은 0이 된다.

smax와 emin이 같은 경우에는 당연히 0이 된다.

 

 

이렇게 설명하니까 약간.. 나조차도 알아보기 힘든데 이럴 때는??!?!? 코드를 보자!

2) 최종 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,s, e;
vector<int>svec; //각 팬들이 학교에 오는 시간
vector<int>evec; // 각 팬들이 학교를 떠나는 시간
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s >> e;
		svec.push_back(s);
		evec.push_back(e);
	}
	sort(svec.begin(),svec.end());
	sort(evec.begin(), evec.end());

	int smax = svec.back(); //팬이 가장 늦게 학교에 오는 시간
	int emin = evec.front(); //팬이 가장 빨리 학교를 떠나는 시간
	if (smax <= emin) cout << 0 << '\n';
	else cout << smax - emin << '\n';
}

3) 참고자료

https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188