Closed changicho closed 4 years ago
링크
N은 최대 50,000 명 이다.
모든 경우를 탐색할 경우, N^2이상의 시간이 소요되며 이는 제한시간 내에 불가능하다.
따라서 NlogN 이내로 풀이를 진행한다.
나가는 순서를 보장하지 않아도 되므로, 정렬을 이용한다.
정렬 후 탐욕 알고리즘을 사용하면 NlogN + N 번 만에 끝낼 수 있으므로 제한시간 내에 충분하다.
몸무게는 최대 240kg 이하이므로 int형으로 선언한다.
먼저 몸무게를 한 기준으로 정렬한다.
시작점과 끝점을 이용해 탐색을 이어간다.
탐색의 경우는 3가지가 존재한다.
시작점과 끝 점이 같은 경우는 탐색이 끝나는 점이다.
한계를 초과한 경우는 끝점의 인원만 보트를 탈 수 있는 경우이다. 따라서 끝점을 이동시킨다.
한계 이하인 경우는 시작점과 끝점인원이 보트를 탈 수 있는 경우이다. 따라서 두 점을 이동시킨다.
42885. 구명보트
링크
설계
시간 복잡도
N은 최대 50,000 명 이다.
모든 경우를 탐색할 경우, N^2이상의 시간이 소요되며 이는 제한시간 내에 불가능하다.
따라서 NlogN 이내로 풀이를 진행한다.
나가는 순서를 보장하지 않아도 되므로, 정렬을 이용한다.
정렬 후 탐욕 알고리즘을 사용하면 NlogN + N 번 만에 끝낼 수 있으므로 제한시간 내에 충분하다.
공간 복잡도
몸무게는 최대 240kg 이하이므로 int형으로 선언한다.
투 포인터
먼저 몸무게를 한 기준으로 정렬한다.
시작점과 끝점을 이용해 탐색을 이어간다.
탐색의 경우는 3가지가 존재한다.
시작점과 끝 점이 같은 경우는 탐색이 끝나는 점이다.
한계를 초과한 경우는 끝점의 인원만 보트를 탈 수 있는 경우이다. 따라서 끝점을 이동시킨다.
한계 이하인 경우는 시작점과 끝점인원이 보트를 탈 수 있는 경우이다. 따라서 두 점을 이동시킨다.
고생한 점