[백준] 1946 신입사원

1. 문제

www.acmicpc.net/problem/1946

1946번: 신입 사원

2. 접근방법

간단한 아이디어가 필요한 문제

 

내가 다른 모든 참가자와 비교해서 서류점수와 면접점수 둘다 나보다 높은 사람이 있다면 떨어지고 그 반대라면 붙을  때 뽑힐 수 있는 신입사원의 수를 구하는 문제

 

서류등수,면접등수

그렇다면 서류등수가 1등인 사람은 서류등수 중 본인 등수 보다 높은 사람이 없으니 무조건 뽑히게 될 것이다.

서류등수가 2등인 사람은?

서류등수가 1등인 사람의 면접등수보다 면접등수가 높다면 뽑힐 수 있을 것이다.

서류등수가 3등인 사람은?

서류등수가 1,2등인 사람들중 면접등수가 가장 높은 등수보다 면접등수가 높다면 뽑힐 수 있을 것이다.

 

 

서류등수,            면접등수

정렬 해놓고 보면

서류 1등은 무조건 뽑힐 것이고

서류 2등은 1등의 면접이 4등인데 본인은 3등이니 뽑힐 것이다.

서류 3등은 서류 1,2등 중 면접 3등이 제일 높은데 본인은 2등이니 뽑힐 수 있다.

서류 4등은 서류 1,2,3등 중 면접 2등이 제일 높은데 본인은 1등이니 뽑힐 수 있다.

서류 5등은 서류 1,2,3,4등 중 면접 1등이 제일 높은데 본인은 5등이니 뽑힐 수 없다.

 

즉 서류등수로 줄을 세워 놓고

본인 서류등수보다 높은 사람들의 면접등수와 비교해서 본인이 더 높다면

서류와 면접 중 하나는 무조건 더 높은 것이니

신입사원으로 뽑힐 수 있을 것이다.

 

이제 이것을 코드로 구현하면 된다.

 

참고로

서류등수로 줄을 세울 때

어차피 중복이 없으니

서류등수를 인덱스로 면접등수를 값으로 해서 저장하면

정렬없이 줄 세우기를 할 수 있다.

3. 자바 코드

package Silver;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P1946신입사원 {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		for(int tc = 0 ; tc < T ; tc++) {
			int N = Integer.parseInt(br.readLine());
			int score[] = new int [N+1];
			for(int i = 0 ; i < N ; i++) {
				st = new StringTokenizer(br.readLine());
				int docu = Integer.parseInt(st.nextToken());
				int inter = Integer.parseInt(st.nextToken());
				score[docu] = inter;
			}
			int min = score[1];
			int cnt = 1;
			for(int i =2 ; i < N+1 ; i++) {
				if(score[i] < min) { 
					cnt++;
					min = score[i];
				}
			}
			System.out.println(cnt);
		}
	}
}

4. 마치며

실버 문제들이 생각보다 아이디어를 내야하는 문제가 많아서 좋은 것 같다.