[BOJ] 백준 [1946] 신입사원 JAVA

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

1946번: 신입 사원

문제

풀이

그리디 문제이다.. 처음엔 lis 알고리즘으로 풀 수 있을줄 알았다 ..왜냐 ..

서류와 면접 성적이 둘다 낮아야한다 => 평행하다 => 증가하는수열 => LIS 알고리즘

하지만 반례가 있었고 , LIS로 풀 수 없다는 것을 깨달았다 .. 

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        while(tc-->0){
            int size = Integer.parseInt(br.readLine());
            int[] arr = new int[size+1];
 
            for(int i=0;i<size;i++){
                String[] input = br.readLine().split(" ");
                int start = Integer.parseInt(input[0]);
                int end = Integer.parseInt(input[1]);
                arr[start] = end;
            }
 
            int result = 1;
            int standard = arr[1];
            for(int i=2;i<=size;i++){
                if(standard > arr[i]){
                    result ++;
                    standard = arr[i];
                }
            }
            System.out.println(result);
        }
    }
}