문제: https://school.programmers.co.kr/learn/courses/30/lessons/42885
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고있습니다.
구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며, 보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한 구명보트의 최소개수를 출력하는 프로그램을 작성하세요.
▣ 입력설명
첫째 줄에 자연수 N(5<=N<=1000)과 M(70<=M<=250)이 주어집니다.
두 번째 줄에 N개로 구성된 몸무게 수열이 주어집니다. 몸무게는 50이상 150이하입니다.
각 승객의 몸무게는 M을 넘지는 않습니다. 즉 탈출을 못하는 경우는 없습니다.
▣ 출력설명
첫째 줄에 구명보트의 최소 개수를 출력합니다.
▣ 입력예제 1
5 140
90 50 70 100 60
▣ 출력예제 1
3
두명만 뽑으면 되니
오름차순 정렬을 해서 가장 무거운 사람이랑 가장 가벼운 사람이랑 짝을 해서
구명보트의 최소 개수를 구하는 것이 합리적여보인다.
만약 둘이 짝을 지었을때 몸무게가 초과 되면 가장 무거운 사람을 혼자 보내버린다.
만약 사람들이 홀수여서 짝이 안생기고 홀로 남는 경우 그대로 보내버리면 된다. <- 이부분 중요!!
근데 이렇게 하면 딱 한 케이스에서 시간초과가 발생한다.
pop()이 사간을 많이 쓰게 된다고 한다.
딱 2명씩만 뽑는 경우이니 투포인터를 생각해본다.
최종 정답