책너두 - 알고리즘 챌린지[5/20] feat. Generator

오늘의 문제 : 용돈관리

---

이분탐색을 활용한 문제였다.

시작값(가장 큰 값)과 끝값(총합)을 구한 이후, mid값을 탐색하였다.

오랜만에 이분탐색 풀이를 리마인드 할 수 있어 좋았다!

import sys
n, m = map(int, sys.stdin.readline().split())
spends = list(map(int, sys.stdin.buffer.read().splitlines()))

start = max(spends)
end = sum(spends)
ans = sum(spends) + 1

while start <= end :
    mid = (start + end) // 2
    cnt = 0
    now = 0
    for spend in spends :
        if now < spend :
            now = mid
            cnt += 1
        now -= spend

    if cnt > m :
        start = mid + 1
    else :
        end = mid - 1
        ans = min(mid, ans)

print(ans)코드를 입력하세요

---

사실, 이번 풀이를 하면서 파이썬의 generator에 대해 다시 공부할 수 있었다.

코테를 풀면서 map()은 보통 input()값을 int형태로 바꿔주려고 사용을 많이 했다.

앞서 받은 spends를 list로 받지 않고 map으로만 받았다.
max(spends)는 문제가 없었으나 sum(spends) = 0 이 출력되었다.

generator는 이전 값을 소비하면, 더 이상 기억하지 않는다(효율적인 메모리 활용)

근데, 이걸 생각안하고 map 객체를 두 번 사용해서 문제가 발생했다..!

이분탐색, generator 모두 되짚어볼 수 있어 좋았다

---

참고 : 제너레이터 - 제대로 파이썬

참고 : [python] map 함수 사용법, 동작원리 및 특징 (예제포함)