[프로그래머스-그리디] 구명보트 JAVA 자바

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

👉 풀이

• 구명보트를 최대한 적게 사용할려면 가장 몸무게가 큰 사람 + 가장 몸무게가 작은 사람 조합이어야 한다. (보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없다는 제한이 있다)

    public int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);
        int length = people.length;
        int min_idx = 0;
        for(int max_idx = length-1; min_idx <= max_idx; max_idx--){
            if(people[min_idx] + people[max_idx] <= limit) min_idx+=1;
            answer+=1;
        }

        return answer;
    }

• people[min_idx] + people[max_idx] <= 100 인 경우 보트에 두명을 태운다. → min_idx를 옮겨 최소 몸무게인 사람을 update한다.
• people[min_idx] + people[max_idx] <= 100 아닌 경우는 min_idx가 그대로이며, 보트에 max_idx인 최대 몸무게인 사람만 태운다. (최대 몸무게인 사람은 for문에서 계속 update됨)
• 즉, 두명을 태우는 경우만 min_idx 업데이트
• 두명을 태우든 한명을 태우든 보트의 수는 증가