구름톤 챌린지 3주 day15 학습 일기

왕 커다란 돋보기 겟

남은 금액 안에서, 과일 당 조각을 몇 개 구매할 수 있는지를 파악하는 문제

 

정렬된 배열을 순회할 것이기에, heapq로 최대힙을 활용했다.

 

[1개당 포만감, 가격(=해당 과일의 최대 조각 수)] 으로 heap에 삽입

(1) 첫번째 요소가 개당 포만감인 이유

 1개당 가격이 1원으로 동일하다. 따라서 1원(1개)당 포만감이 큰 과일을 먼저 구매하기 위해서였다.

(2) 두번째 요소가 가격인 이유

 실제로 입력으로 들어온 P값을 넣어주었고, 가격이라고 표현했다. 하지만 한 조각의 가격이 1원이기 때문에, 과일 하나는 P개 만큼의 조각을 갖고있다. 따라서 과일의 최대 조각 개수를 의미한다.

 남은 돈 내에서 구매 가능한 최대 조각 수를 구하기 위해 두번째 요소로 사용

(3) 첫번째에 포만감을 넣고 두번째에 가격을 배치한 이유

 heapq에 삽입해서 내부적으로 정렬이 될 때, 첫번째 요소를 기준으로 먼저 정렬을 한다.

 그러나 첫번째 요소가 같을 경우 두번째 요소로 비교하게 된다. 이 문제에서는 특별하게 두번째 요소를 기준으로 정렬하지는 않아도 되지만, 두번째 요소가 큰 것을 더 앞에 배치하게 되면 더 많이, 더 큰 금액으로 구매할 수 있기 때문에 반복문을 조금이라도 더 적게 순회할 수 있다.

 

그리고 heappop()을 하면서 최대 N번을 pop하고, 남은 금액과 구매 가능한 조각 개수(한조각 당 1원)를 비교한다.

(1) 남은 금액보다 조각 수가 적거나 같은 경우, 최대 조각 개수로 구매가 가능하다.

(2) 그러나 남은 금액보다 조각 수가 많은 경우, 남은 금액 만큼만 구매한다.

 

early return이 가능하기도 한데, 과일 조각 수가 남은 금액보다 크거나 같은 경우에는

금액과, 포만감에 대한 연산을 마친 뒤에 반복문을 종료해주면 된다.

 

오늘의 학습 일기 끝