99클럽 코테 스터디 19일차 TIL , 구명보트

문제

풀이

사람들의 몸무게와 구명보트의 제한무게가 주어진다.

구명보트는 최대 두 사람까지 탈 수 있다.

구명보트가 최소 몇개 필요한지 return 하면 된다.

제출 1 - 정답

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int lt = 0;
        int rt = people.length - 1;

        while(lt <= rt){
            if(people[lt] + people[rt] <= limit){
                lt++;
                rt--;
            }else{
                rt--;
            }
            answer++;
        }

        return answer;
    }
}

 

무거운 사람은 무조건 타게 된다.

무조건 타게 되는 무거운 사람과 가벼운 사람의 합이 제한 무게를 넘지 않으면 같이 탄다.

제한조건의 무조건 두 명만 탄다는 조건이 중요한 것 같다.

TIL

• "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 그리디 알고리즘의 정의에 대해 다시 한번 상기했다.