[Greedy] 구명보트

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

 

 

그리디 알고리즘

- 최적의 값을 구해야 하는 상황에서 사용되는 근시안적인 방법론으로 

   ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘이다.

 

- 이때, 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 하고 있다.

- 주로 문제를 분할 가능한 문제들로 분할한 뒤,

   각 문제들에 대한 최적해를 구한 뒤 이를 결합하여 전체 문제의 최적해를 구하는 경우에 주로 사용된다.

 

 

위 문제에서, 주목해야 할 포인트가 몇가지 있다.

1. 구명보트는 최대 2명씩 밖에 탈 수 없다.

2. 2명이 탈때, 문제에서 주어지는 무게제한(limit)를 넘길 수 없다.

3. 필요한 구명보트 개수가 최솟값이 되도록 한다.

 

 

그럼 구명보트 개수가 최솟값이기 위해서,

최대한 2명씩 짝지어서 태워야 하고,

그러기 위해서는 가장 가벼운 사람과 가장 무거운사람이 짝 지어야 무게제한을 넘지 않을 확률이 높아진다.

 

정리해보면,

1. 오름차순 정렬을 통해 가장 가벼운 무게 ~ 가장 무거운 무게 순으로 정렬한다.

2. 가장 가벼운 무게와 가장 무거운 무게의 합이 limit을 넘는지 비교한다.

3. 넘을경우, 가장 가벼운 무게와 두번째로 무거운 무게의 합이 limit을 넘는지 비교한다.

4. 넘지 않을경우 가벼운 무게의 인덱스(start)를 하나 올려주고, 무거운 무게 인덱스(end)를 하나 내려준다.

5. 이렇게 비교하여, (총 사람수 - 2명씩 탄 보트의 수(start) ) 를 하면 사용된 보트의 최솟값이 나온다.

 

 

코드

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int n=people.length;
        int start = 0;
        int end = n-1;
        
        Arrays.sort(people);
        
        while(end > start){
            if(people[start]+people[end]<=limit){
                start++;
                end--;
            }
            else{
                end--;
            }
        }
        int answer = n-start;
        return answer; //start의 개수가 2명이 한배에 탄 경우의 수이므로. 나머지는 각배임.
    }
}

 

 

[참고]

https://adjh54.tistory.com/212#google_vignette