구명보트

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

코딩테스트 연습 - 구명보트

문제 풀이 방법

제일 큰거부터 차례대로 내려오며 제일 작은것과 합쳤을때 제한을 넘지않으면 같이보내고 아니면 같이보내는 방식으로 진행한다

왜냐 제일큰것이 제일작은것이랑 합쳤는데 넘는다면 다른 것도 안되기때문이다..

이걸 생각하지못했음 흠.. 어떻게 이걸 생각해내는걸까.. 

 

맨처음에는 그냥 정렬후 작은거부터 보냈는데 잘못생각했음 2명이라는 제한이 있는걸 제대로 보지않았고 

그로 인해 제일 큰거부터 보내야된다는 생각 조차하지못한듯 

맨처음 코드 작성은 그냥 작은거부터 다 더해서 제한 안넘으면 다태워보내는방식으로 해버림

 

그리고 풀면서 어 이거 그리디 알고리즘이내? 하는 그런걸 느끼지 못했음 흠냐.. 질문좀 해야겠다

 

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int i=people.length-1;
        
        
        //2명만 태울수있음 
        // 제일뒤에꺼랑 제일앞에꺼랑 더했는데 안된다 그러면 그냥 혼자보내야되는거임
        //왜냐 제일작은거랑더했는데도 안되면 그다음숫자는 무조건안되니까
        
        int j=0;// 시작 index
        int num=0;// limit와 비교하기위한 변수 선언
        while(i>=j)
        {
            num = people[j]+people[i];
            if(num<=limit)//제한을 넘지않으면 같이보냄
            {
                answer++;
                j++;
                i--;
            }
            else
            {
                answer++;
                i--;
            }   
        }      
        return answer;
    }
}

//구명보트 최대한 적게 사용해서 모든사람을 구출하려고함