Programmers / 2단계 / 구명보트 / python

 

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

나의 풀이 (22.2점 실패)

def solution(people, limit):
    people.sort()
    wsum=people[0]#50
    count=1
    for i in range(1, len(people)): #50 70 80 
        if wsum+people[i]==limit: 
            count+=1
            wsum=0
        elif wsum+people[i]>limit:
            count+=1
            wsum=people[i]
        else:
            wsum+=people[i]
    return count

 

 

모범 답안

def solution(people, limit) :
    count = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            count += 1
        b -= 1
    return len(people) - count

나는 정렬 후 앞에 작은 두 사람의 무게를 더하여 limit와 비교하는 것으로 접근하였는데 이렇게 접근하게 되면 people = [ 40 50 50 60 ] 일 때 보트는 최소 2개가 필요하지만 내 코드로는 count = 3이 나온다. 따라서 가장 가벼운 앞의 두 사람이 아닌, 가장 가벼운 사람과 가장 무거운 사람 투 포인트로 접근하여 마지막에 두 사람을 묶어서 조건 안에 들어가는 경우는 2명이 한 보트로 처리되기 때문에 전체에서 그 경우를 빼준다.