탐욕법(Greedy)-구명보트 [JAVA]

탐욕법?

• "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"
• ‘각 단계에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘

프로그래머스 구명보트 문제

다음 구명보트 문제를 풀기 위해
큰수를 먼저 제거하기 위해 배열을 정렬한 후 for문을 돌려주었다.

Arrays.sort(people);    							//배열 정렬
        int cnt=0;		
        int  j =0;
        for (int i = people.length-1; i>=j;i--){   
            if (people[i] + people[j] <= limit){	//가장 큰수와 가장 작은수의 합이 limit 이하면 cnt + 1
                cnt += 1;
                j += 1;
            }
            else if(i == 0){						//i가 0인 경우는 마지막 하나 남은 경우, cnt + 1
                cnt += 1;
                break;
            }
            else cnt += 1;						    //모두 각각 한명씩 보트에 타는 경우 cnt + 1
        }