[프로그래머스 | 파이썬3] 구명보트- 그리디알고리즘 활용

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

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

> 그리디알고리즘 활용

 

최소값에서부터 시작해서 반복문을 돌리며 end값과 최소값과 더했을 때 limit을 넘어가는지 안넘어가는 지를 그때그때마다 체크해서 limit을 안넘어가게 될 때 최소값을 올려줘서 계속 탐색함 -> 현재 주어진 상황에서 가장 좋은것만 고르는 그리디 알고리즘 활용

def solution(people, limit):
    answer=0
    people.sort()
    start= 0
    end= len(people)-1
    while start<=end:
    	# 최소값과 end값을 더했을 때 limit보다 크면 end값은 혼자서밖에 보트를 탈수밖에 없는 
        #몸무게이기 때문에 보트의 개수를 하나씩 늘려줘야함
        answer+=1
        # 둘을 더한 값이 limit보다 작거나 같을때 둘을 함께 태울 수 있으므로 둘은 태우고 start값을 한칸 올려줌
        if people[start]+people[end] <= limit:  
            start+=1
        end-=1
            
    return answer