[알고리즘] 백준 1946번: 신입 사원 (C++), 그리디 알고리즘

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

1946번: 신입 사원

---

들어가기 앞서

어느 날 보니 다른 기초 알고리즘들은 최소 한 개라도 포스팅이 있는데 그리디만 없었다.

어떻게 보면 코테나 좋은 PS를 위해서 구현, 그리디, DP, 문자열 등은 완전 마스터해야 한다고 생각하는데

(주관적인 생각으로 다른 알고리즘들은 기법이자 프레임이지 위에 언급한 키워드들은 모두 생각에 의존을 많이 하기 때문이다.)

그렇다고 아예 그리디 문제를 안 풀었던 건 아니다. 다른 알고리즘 문제들을 풀면서 그리디가 살짝 섞인 문제들을 많이 겪었기 때문이다.

이번 기회에 정리해두자!

---

그리디 알고리즘 (Greedy Algorithm)

(https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)

최적의 해를 구하는 알고리즘인데 무조건 최적의 해는 보장하지 않는다는 것을 기억해두어야 한다.

그리디의 대표 문제로 거스름돈이 있지만

(BOJ 동전 1: https://www.acmicpc.net/problem/2293)

2293번: 동전 1

이 문제는 그리디로 풀 수 없다. (DP Coin change 알고리즘으로 풀 수 있다.)

왜냐하면 이건 그리디와 DP의 차이점인데

그리디는 순간적으로 최적의 해를 구한다는 장점이 있지만 그것이 최적의 해는 될 수 없다는 단점이 있고,

DP는 모든 상황을 고려한다는 단점이 있지만 최적의 해가 된다는 것이 차이점이기 때문이다.

>> 즉, 그리디로 최적의 해를 구하려면 최적의 해를 도출할 수 있는가를 확인해야 한다.

 

사실 이게 그리디의 설명 끝이다. 이것만 보았을 때는 그리디에 감이 잘 안 온다 풀어보아야 한다.

그리디나 DP, 구현 같은 문제들은 역시 겪어봐야 안다.

---

문제

0)

조건: 적어도 하나만 남들보다 순위가 뒤떨어지는 게 있어야 합격이다.

>> 2개 다 뒤떨어지면 불합격이라는 뜻

 

1)

pair 자료형을 사용해서 first(서류 심사 순위)의 오름차순으로 정렬을 해주었다.

(처음에는 순위가 아닌 점수로 봐서 헷갈렸었다.)

이렇게 되면 맨 첫 원소는 무조건 합격이다. 서류 심사 1등으로 면접 심사 등수가 어떻든 적어도 하나만 남들보다 순위가 뒤떨어지는 조건에 포함되기 때문이다.

 

2)

그리고, 어떠한 서류 심사 N등이 있을 때, 서류 심사 1 ~ N - 1등을 한 사람들보다 면접 심사에서 한 명이라도 순위가 높은 사람이 있다면 불합격이다.

>> 서류, 면접 두 개 다 높은 사람이 존재한다. >> 조건 위배

 

여기서 코드를 잘못 짜서 틀렸었는데 다음 코드가 문제였다.

int result = 0;
for (int i = 1; i < arr.size(); i++) {
	if (arr[i - 1].second > arr[i].second) {
		result++;
	}
}
cout << result + 1 << '\n';

왜 이 코드가 문제가 되냐면 바로 직전의 원소만 비교를 해주기 때문이다.

>> 앞선 등수'들' 중에 한 명이라도 면접 한 등수가 높다면 탈락이다.

 

반례도 만들어 보았다.

[input]
1
3
1 1
2 3
3 2
[output]
2
[answer]
1

 

그럼 2중 for문으로 해보자. (이해를 돕기 위해 구현)

int result = n;
for (int i = 0; i < arr.size(); i++) {
	for (int j = 0; j < i; j++) {
		if (arr[j].second < arr[i].second) {
			result--;
			break;
		}
	}
}
cout << result << '\n';

이 코드가 답임에도 불구하고, 답이 될 수 없는 이유는 N의 범위가 1 <= N <= 100,000이기 때문에 시간 복잡도는 O(N^2)가 될 것이고, 시간 초과가 난다.

 

그럼 어떻게 하면 되는가?

>> 직전의 등수들에서 제일 작은 등수를 기억해두자.

우선 시작은 0번째부터이기 때문에 limit 변수에다가 1번째 등수 값을 할당해주자.

>> limit을 넘은 등수를 가졌다면 탈락

>> limit보다 작은 등수를 가졌다면 합격과 동시 그다음 등수들은 limit이 바뀌게 된다.

int cnt = 0;
int limit = arr[0].second;
for (int i = 1; i < n; i++) {
	if (arr[i].second < limit) {
		cnt++;
		limit = arr[i].second;
	}
}

 

그러고 나서 맨 첫 번째 등수도 포함시켜줘야 하기 때문에 cnt + 1을 해준다.

[AC 코드]

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#define pii pair<int, int>
using namespace std;

bool cmp(pii a, pii b) {
	return a.first < b.first;
}

int T;
int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		int n;
		cin >> n;
		vector<pii> arr;
		for (int i = 0, a, b; i < n; i++) {
			cin >> a >> b;
			arr.push_back({ a, b });
		}
		sort(arr.begin(), arr.end(), cmp);

		int cnt = 0;
		int limit = arr[0].second;
		for (int i = 1; i < n; i++) {
			if (arr[i].second < limit) {
				cnt++;
				limit = arr[i].second;
			}
		}

		cout << cnt + 1 << '\n';
	}
	return 0;
}