ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 1946
    알고리즘/acmicpc 2015. 10. 16. 02:03

    진짜 문제를 무지하게 꼼꼼히 읽어야 한다. 문제 잘못 이해하면 바로 틀린다. 이 문제를 풀때 나는 생각보다 빨리 서류심사 결과 또는 면접 성적으로 정렬해야 하는것을 깨달았다. 


    하지만 여기서 부터 꼬이기 시작했는데 서류심사 1등의 면접 성적 만큼 뒤에있는 서류 심사 순위는 모두 커버된다는 괴상한 논리를 펴기 시작했다. 서류 심사가 떨어지고 면접심사도 동시에 떨어질 수 잇는 것인데도 나는 혼자만의 논리에 빠져서 이상하게 문제를 질질 끌었다..


    예제문제부터 제대로 풀지 않았다. 누구 누구가 합격한다는 힌트만 줘도 이렇게 뻘짓은 하지 않았을 것 같다. 하지만 뭐 이건 내 실수니...


    문제자체는 많이 어렵지는 않았던 것 같다. 일단 서류 순위로 정렬한다. 서류 1등은 면접과 상관없이 독보적이므로 무조건 포함될 수 밖에 없다. 그 뒤로는 서류 순위대로 추가해주는데 이떄 자신의 앞에 있는 애보다 면접 순위가 높아야 한다. 추가 할 때마다 면접 순위를 계속 업데이트 해주어서 O(N)에 해결 할 수 있다.


    하 그건 그렇고 이렇게 뻘짓해서 시간 보내니 정말 아쉽다... 실전에는 이러면 안되는데...


     
    #include<cstdio>
    #include<algorithm>
    
    #include<fstream>
    
    using namespace std;
    
    pair<int, int> d[100005];
    
    int main(){
    	int tc;
    
    	ifstream ifp("input.txt");
    
    	ifp>>tc;
    	//scanf("%d", &tc);
    
    	while(tc--){
    		int n;
    
    		ifp>>n;
    		//scanf("%d", &n);
    		for(int i=0; i<n; i++)
    			ifp>>d[i].first>>d[i].second;
    			//scanf("%d %d", &d[i].first, &d[i].second);
    		sort(d, d+n);
    
    		int ends = d[0].second;
    		int res = 1;
    
    		for(int piv=1; piv<n; piv++){
    			if(d[piv].second < ends){
    				res++;
    				ends = d[piv].second;
    			}
    		}
    		printf("%d\n", res);
    	}
    
    	return 0;
    }
    

    '알고리즘 > acmicpc' 카테고리의 다른 글

    4307  (0) 2015.10.17
    1577  (0) 2015.10.16
    2590  (0) 2015.10.15
    1931  (0) 2015.10.14
    11000  (0) 2015.10.11

    댓글

Designed by Tistory.