[백준 / BOJ] 14464 소가 길을 건너간 이유 4

문제

출처 : www.acmicpc.net/problem/14464

14464번: 소가 길을 건너간 이유 4

N마리의 소 C마리의 닭이있다.

각 소는 a초부터 b초까지 길을 건널수있는데, 이때 닭이 소를 도와준다면 한번에 길을 건널수있다.

닭은 정확히 T초에만 소를 도와줄수있다.

소는 최대 한마리만 닭의 도움을 받을수있고, 닭역시 최대 한마리의 소만 도와줄수있다. 이때 도움 받을수 있는 소가 몇마리인지 출력하는 문제다.

 

풀이

닭이 한번 도와줬다면 다시 도와줄수없으니,

먼저 길을 건너기 시작하는 소중에 빨리 건너는소를 도와주면된다.

 

소를 pair를 사용해

{시작하는 초, 끝나는 초}로 저장하고 오름차순 정렬하면, (먼저 시작하는소중에 빨리 건너는소)이 처럼 정렬된다.

예를들어, 소가

{1,1} {3,1} {1,4} {1,3} 이렇게 입력되었을때, 이를 오름차순 정렬하면

{1,1} {1,3} {1,4} {3,1} 이런식으로 정렬된다.

 

닭도 마찬가지로 가장 먼저 도와줄수있는 닭부터 도와줘야하므로 오름차순 정렬해준다. 

닭의 숫자만큼 완전탐색으로 돌려주며, 닭이 소를 도와줄수있다면 도와주고 해당 소를 체크한다. 그후 바로 다음 닭으로 넘어가서 다음 닭이 도와줄수있는 소를 찾아주면 된다. 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14464%20%EC%86%8C%EA%B0%80%20%EA%B8%B8%EC%9D%84%20%EA%B1%B4%EB%84%88%EA%B0%84%20%EC%9D%B4%EC%9C%A0%204/main.cpp

devxb/JJUNalgo