﻿ ( 문제 ) 쿠키 포장 하 기 | Jacob ' s Coding Playground 
 ( 문제 ) 쿠키 포장 하 기 
 [ 문제 출처 : Codechef ] 쿠키 를 만드 는 공장 에서 다양 한 무게 의 N 개 의 쿠키 들 을 만들 었 습니다 . 그리고 쿠키 를 하나 씩 포장 할 상자 들 또한 N 개 를 만들 었 습니다 . 하지만 안타깝 게 도 매니저 가 그렇게 현명 하 지 못해서 상자 가 포장 할 수 있 는 쿠키 의 무게 에 한계 가 있 다고 합니다 ㅠㅠ N 개 의 쿠키 들 의 무게 와 , N 개 의 상자 들 이 포장 할 수 있 는 한계 무게 가 주어졌 을 때 , 최대 로 포장 할 수 있 는 쿠키 의 수 를 구해 주 세요 . 
 예 를 들 면 , 쿠키 의 무게 가 [ 10 , 30 , 20 ] 으로 주어졌 고 , 상자 가 담 을 수 있 는 한계 무게 가 [ 30 , 10 , 20 ] 으로 주어졌 을 때 , 우리 는 최대 3 개 의 쿠키 모두 를 각각 의 상자 에 담 을 수 있 습니다 . ( 10 을 10 , 20 을 20 , 30 을 30 에 할당 했 을 경우 ) 어떻 게 이 최대 쿠키 개수 를 찾 을 수 있 을까요 ? 
 방법 은 바로 Sorting 을 활용 하 는 것 입니다 ! 각각 쿠키 들 의 무게 와 상자 의 한계 무게 를 오름차순 으로 정렬 했 다고 가정 해 봅시다 . 그러 고 나 면 가장 작 은 무게 부터 들어갈 수 있 는 가장 작 은 상자 를 찾 기 시작 합니다 . 어차피 상자 하나 에 하나 의 쿠키 만 넣 을 수 있 기 때문 에 , 이런 식 으로 넣 는 경우 우리 는 바로 넣 을 수 있 는 최대 쿠키 의 개수 를 구할 수 있 게 됩니다 . 이 때 는 Sorting 하 는 데 필요 한 $ O ( n \ log n ) $ 과 각각 넣 을 수 있 는지 파악 하 기 위한 $ O ( n ) $ 만 필요 하 기 때문 에 팩토리 얼 과 는 비교 도 할 수 없 을 정도 로 빠르 게 계산 하 게 됩니다 . 
 이제 코드 를 살펴보 면 , 
 def maxNumPack ( w , l ) : 
 # 먼저 정렬 을 하 구요 , 
 for weight in w : # 작 은 무게 부터 꺼내 보 고 , 
 while ind < len ( l ) and weight > l [ ind ] : # limit 이 현재 무게 보다 더 큰 것 이 나올 때 까지 다음 limit 으로 옮깁니다 . 
 # 상자 가 남 아 있 으면 , 현재 물건 을 담 고 다음 물건 을 살펴봅니다 . 
 >>> print maxNumPack ( [ 10 , 30 , 20 ] , [ 30 , 10 , 20 ] ) 
 >>> print maxNumPack ( [ 9 , 7 , 16 , 4 , 8 ] , [ 8 , 3 , 14 , 10 , 10 ] ) 
 결과 값 이 잘 나옴 을 확인 하 실 수 있 죠 ? 은근히 정렬 을 이용 한 빠른 해결책 들 이 많 기 때문 에 알고리즘 에 잘 적용 할 수 있 도록 많이 익숙 해 지 시 길 바랍니다 : )