[PCCP] 그리디 알고리즘 - 최대 사과의 개수 | 파이썬

코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

그리디 알고리즘 - 최대 사과의 개수

앞서 공부한 그리디 알고리즘을 사용해 최대 사과의 개수 문제를 풀어보겠다.

---

문제

여러 종류의 사과박스가 있습니다.
각 박스의 종류에 따라 박스에 담겨있는 사과의 개수가 다릅니다.
트럭에 박스를 실으려고 합니다. 트럭에 박스을 실을 수 있는 최대 개수 제한이 있습니다.
매개변수 box에 각 박스 종류의 정보가 주어지고, limit에 트럭의 실을 수 있는 박스의 최대 개수가 주어지면 트럭에 실을 수 있는 사과의 최대 개수를 반환하는 프로그램을 작성하세요.

---

입출력 예

box	limit	answer
[[2, 20], [2, 10], [3, 15], [2, 30]]	5	115
[[1, 50], [2, 20], [3, 30], [2, 31], [5, 25]]	10	302
[[3, 40], [5, 20], [5, 70], [1, 80], [5, 30], [3, 35]]	15	745
[[2, 70], [5, 100], [3, 90], [1, 95]]	8	775
[[80, 20], [50, 10], [70, 15], [70, 30], [80, 70], [90, 88], [70, 75]]	500	23920

---

제한사항

• 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 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))

---

풀이

1. 먼저 box의 사과의 개수를 기준으로 내림차순 정렬
2. limit를 넘어가는 걸 방지하기 위해 min으로 박스의 개수 설정
3. 박스 수(cnt) * 사과의 개수를 answer에 플러스
4. 트럭에 실은 박스 수만큼 limit에서 마이너스
5. 만약 트럭에 박스가 가득 차면 break 후 최종적으로 트럭에 실은 사과의 개수 return