[그리디] -최대 사과의 개수

최대 사과의 개수

여러 종류의 사과박스가 있습니다.
각 박스의 종류에 따라 박스에 담겨있는 사과의 개수가 다릅니다.
트럭에 박스를 실으려고 합니다. 트럭에 박스을 실을 수 있는 최대 개수 제한이 있습니다.

매개변수 box에 각 박스 종류의 정보가 주어지고, limit에 트럭의 실을 수 있는 박스의 최대 개수가 주어지면 트럭에 실을 수 있는 사과의 최대 개수를 반환하는 프로그램을 작성하세요.

제한사항:
• box의 길이는 100,000을 넘지 않습니다.
• box[i][0]은 i 종류 박스의 개수, box[i][1]은 i 종류의 박스 한 개에 들어 있는 사과의 개수 입니다. 서로 다른 종류의 박스라도 담아 있는 사과의 개수는 같을 수 있습니다.
• 1 <= box[i][0] <= 100, 1 <= box[i][1] <= 100
• 1 <= limit <= 10,000,000

 

나의 코드

def solution(box, limit):
    answer = 0
    box.sort(key= lambda x: -x[1])
    
    for x in box:
        if limit>=x[0]:
            limit=limit-x[0]
            answer=answer+x[1]*x[0]
        elif limit <x[0]:
            answer=answer+x[1]*limit
            break

    return answer
    
                                           
print(solution([[2, 20], [2, 10], [3, 15], [2, 30]], 5))
print(solution([[1, 50], [2, 20], [3, 30], [2, 31], [5, 25]], 10))
print(solution([[3, 40], [5, 20], [5, 70], [1, 80], [5, 30], [3, 35]], 15))
print(solution([[2, 70], [5, 100], [3, 90], [1, 95]], 8))
print(solution([[80, 20], [50, 10], [70, 15], [70, 30], [80, 70], [90, 88], [70, 75]], 500))

최대한 많은 갯수를 담기 위해 [사과종류,사과갯수]의 원소를 사과 갯수를 역정렬하여 많은 갯수 부터 담도록 하였고  Limit보다 사과종류가 더 적은 경우를 분기 처리 하였다.

 

 

정답 코드

def solution(box, limit):
    answer = 0
    box.sort(key = lambda v : -v[1])
    for x in box:
        cnt = min(limit, x[0])
        answer += (cnt * x[1])
        limit -= cnt
        if limit == 0:
            break
    
    return answer
    
                                           
print(solution([[2, 20], [2, 10], [3, 15], [2, 30]], 5))
print(solution([[1, 50], [2, 20], [3, 30], [2, 31], [5, 25]], 10))
print(solution([[3, 40], [5, 20], [5, 70], [1, 80], [5, 30], [3, 35]], 15))
print(solution([[2, 70], [5, 100], [3, 90], [1, 95]], 8))
print(solution([[80, 20], [50, 10], [70, 15], [70, 30], [80, 70], [90, 88], [70, 75]], 500))

정답 코드도 같은 로직을 구성하였지만 cnt의 하나의 변수로 answer를 합해주어서 더 가독성이 좋은것 같다.