[C/C++] 백준 1946번 - 신입 사원

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int T, N, a, b;
int Rank[100001]; 
// rank[a] = b 는 서류등수가 a인 사람의 면접 등수는 b라는 의미

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;

	while (T--)
	{
		cin >> N;

		for (int i = 0; i < N; i++)
		{
			cin >> a >> b;
			Rank[a] = b;
		}

		int ans = 1;
		int tmp = Rank[1];

		for (int i = 2; i <= N; i++)
		{
			if (Rank[i] < tmp)
			{
				tmp = Rank[i];
				ans++;
			}
		}
		cout << ans << '\n';
	}
}

 

 

풀이 방법

 

Rank[a] = b의 의미는 서류 등수가 a등인 사람의 면접 등수는 b라는 의미.

 

그리고 등수는 겹치지 않기 때문에 서류 등수를 인덱스로 하고 해당 값을 면접 값으로 저장한다.

서류 1등의 경우, 만약 면접등수가 꼴찌라도 서류 등수가 1등이므로 무조건 채용된다.
그리고 서류 1등의 면접 등수를 tmp로 저장한다.

다음 서류 2등의 경우, 서류 1등의 면접 등수보다 높아야 채용되며
채용 된다면 tmp는 서류 2등의 면접 등수로 갱신된다.

 

예제 입력 2를 예시로 들자면,

서류등수	1	2	3	4	5	6	7
면접등수	4	5	6	2	7	1	3

서류 1등의 면접 등수는 4이므로 (ans = 1, tmp = 4)

서류 2등의 면접 등수는 5이고 tmp보다 크므로 pass (ans = 1, tmp = 4)

서류 3등의 면접 등수는 6이고 tmp보다 크므로 pass (ans = 1, tmp = 4)

서류 4등의 면접 등수는 2이고 tmp보다 작으므로 채용 (ans = 2, tmp = 2)

서류 5등의 면접 등수는 7이고 tmp보다 크므로 pass (ans = 2, tmp = 2)

서류 6등의 면접 등수는 1이고 tmp보다 작으므로 채용 (ans = 3, tmp = 1)

서류 7등의 면접 등수는 3이고 tmp보다 크므로 pass (ans = 3, tmp = 1)

 

 

www.acmicpc.net/problem/1946

1946번: 신입 사원