[그리디]구명보트

🔗 문제 링크

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

✔️ 소요된 시간

1시간

✨ 수도 코드

0. 문제에서 주어진 상태

1. 몸무게 순서대로 정렬한다.

2. 가장 무거운 사람을 태운다.

3. 최대 2명을 태울 수 있으므로 남은 자리에 태울 수 있는 사람을 알아본다.

• 가장 가능성이 높은 사람은 가장 무게가 작은 사람이므로, 가장 몸무게가 작은사람과 가장 몸무게가 많은 사람의 합이 제한을 넘지 않는지 확인한다.
• 제한을 넘지 않는다면 두 명을 태운다.
• 제한을 넘으면, 가장 무거운 사람 혼자 태운다.
  

  

  
  
  
• 3. 최대 2명을 태울 수 있으므로 남은 자리에 태울 수 있는 사람을 알아본다.

 

 

소스코드

def solution(people, limit):
    count=0
    people.sort()
    start=0
    end=len(people)-1

    while start<=end:
        if people[start]+people[end]<=limit:
            start+=1
            end-=1
        else:
            end-=1
        
        count+=1
    
    return count

• start와 end는 이미 정렬된 리스트에서 가장 무게가 작은사람과 많은 사람을 나타내는 인덱스
• if 무게가 적은사람과 무게가 많은 사람의 합이 제한 무게보다 적게 나가면 start, end 를 변경.
• else 무게가 적은사람과 무게가 많은 사람의 합이 많이나가면 무거운사람 혼자만 태우므로 end만 변경

 

📚 새롭게 알게된 내용

 

• 문제의 조건을 꼼꼼히 읽어야겠다고 생각, 처음에 최대 2명인지 확인안하고 문제 품.
• 참고한 블로그 : https://jongwoon.tistory.com/100